# 543

from utils.treeNode import TreeNode

# time: O(N)
# space: O(N)
class Solution:
    def dimater(self, root):
        self.result = 0
        if not root:
            return self.result
        
        def depth(root):
            left_depth = 1 + depth(root.left) if root.left else 0
            right_depth = 1 + depth(root.right) if root.right else 0
            self.result = max(self.result, left_depth + right_depth)

            return max(left_depth, right_depth)
            
        depth(root)
        return self.result


# time = O(N)
# space = O(N)
class Solution2:
    heights_map = dict()

    def dimater(self, root):
        if not root:
            return 0
        
        return max(
            self.height(root.left) + self.height(root.right),
            self.dimater(root.left),
            self.dimater(root.right)
        )
    
    def height(self, root):
        if not root:
            return 0
        
        if root in self.heights_map:
            return self.heights_map[root]
        
        height = 1 + max(self.height(root.left), self.height(root.right))
        self.heights_map[root] = height

        return height

one = TreeNode(1)
two = TreeNode(2)
three = TreeNode(3)
four = TreeNode(4)
five = TreeNode(5)
six = TreeNode(6)
seven = TreeNode(7)

one.left = two
two.left = three
three.left = four
two.right = five
five.right = six
six.right = seven

print(one)
print('===============')

solution = Solution()
print(solution.dimater(one))

class SOlution:
    def get_diameter(self, root):
        depth_map = dict()

        if not root:
            return 0
        
        def depth(root):
            if not root:
                return 0
            
            if root in depth_map:
                return depth_map[root]
            
            result = 1 + max(depth(root.left), depth(root.right))
            depth_map[root] = result
            
            return result
        
        return max(
            1 + depth(root.left) + depth(root.right),
            self.get_diameter(root.left),
            self.get_diameter(root.right)
        )
