Algorithm - Tree (1)

Leetcode Tree problem collection (1)

• 104.Maximum Depth of Binary Tree
• 98.Validate Binary Search Tree
• 101.Symmetric Tree
• 102.Binary Tree Level Order Traversal
• 108.Convert Sorted Array to Binary Search Tree

Inorder (Left, Root, Right)
Preorder (Root, Left, Right)
Postorder (Left, Right, Root)

104. Maximum Depth of Binary Tree

DFS:

def maxDepth(self, root: TreeNode) -> int:
    if not root:
        return 0
    left, right = 0, 0
    if root.left:
        left = self.maxDepth(root.left)
    if root.right:
        right = self.maxDepth(root.right)
    return max(left, right) + 1

BFS:

def maxDepth(self, root: TreeNode) -> int:
    if not root:
        return 0
    q = [(root, 1)]
    depth = 0
    while q:
        cur, d = q.pop()
        depth = max(d, depth)
        if cur.left:
            q.append((cur.left, d + 1))
        if cur.right:
            q.append((cur.right, d + 1))
    return depth

98. Validate Binary Search Tree

This one is interesting

def isValidBST(self, root: TreeNode,  floor=float('-inf'), ceil = float('inf')) -> bool:
    if not root:
        return True
    if floor < root.val < ceil:
        return self.isValidBST(root.left, floor, root.val) and self.isValidBST(root.right, root.val, ceil)
    return False

101. Symmetric Tree

def isSymmetric(self, root: TreeNode) -> bool:
    q = [root, root]
    while q:
        right = q.pop()
        left = q.pop()
        
        # empty sub tree
        if not left and not right:
            continue
        if (left and not right) or (not left and right) or (left.val != right.val):
            return False
            
        # mirror check
        q += [left.left, right.right, left.right, right.left]
        
    return True

102. Binary Tree Level Order Traversal

BFS

def levelOrder(self, root: TreeNode) -> List[List[int]]:
    if not root:
        return []
    
    q = [root]
    cur_nodes = 1
    child_nodes = 0
    res = []
    cur = []
    
    while q:
        node = q.pop(0)
        cur_nodes  -= 1
        cur.append(node.val)
        
        if node.left:
            q.append(node.left)
            child_nodes += 1
        
        if node.right:
            q.append(node.right)
            child_nodes += 1
        
        if cur_nodes == 0:
            res.append(cur)
            cur = []
            cur_nodes = child_nodes
            child_nodes = 0
    return res

DFS

def levelOrder(self, root: TreeNode) -> List[List[int]]:
    levels = []
    if not root:
        return levels
    
    def dfs(node, level):
        if len(levels) == level:
            levels.append([])

        # append the current node value
        levels[level].append(node.val)

        # process child nodes for the next level
        if node.left:
            dfs(node.left, level + 1)
        if node.right:
            dfs(node.right, level + 1)
        
    dfs(root, 0)
    return levels

108. Convert Sorted Array to Binary Search Tree

Typical DFS

def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
    if not nums:
        return None
    
    i = int(len(nums) / 2)
    node = TreeNode(nums[i])
    node.left = self.sortedArrayToBST(nums[: i])
    node.right = self.sortedArrayToBST(nums[i + 1: ])
    return node