Leetcode Tree problem collection (2)

  • 199.Binary Tree Right Side View
  • 105.Construct Binary Tree from Preorder and Inorder Traversal
  • 236.Lowest Common Ancestor of a Binary Tree
  • 987.Vertical Order Traversal of a Binary Tree
  • 103.Binary Tree Zigzag Level Order Traversal

Basic About Tree:
Preorder: root - left - right
Inorder: left - root - right
Postorder: left - right - root

199. Binary Tree Right Side View

dfs, root -> right -> left

1
2
3
4
5
6
7
8
9
10
11
12
13
def rightSideView(self, root: TreeNode) -> List[int]:
    res = {}
    
    def dfs(node, level = 1):
        if not node:
            return
        if level not in res:
            res[level] = node.val
        dfs(node.right, level + 1)
        dfs(node.left, level + 1)
    
    dfs(root)
    return list(res.values())

105. Construct Binary Tree from Preorder and Inorder Traversal

get root from 1st level of preorder
get child inorder by deviding inorder by root.val
get child preorder by number of child inorder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
    if not preorder:
        return None
    
    root = TreeNode(preorder.pop(0))
    i = inorder.index(root.val)
    
    left_inorder = inorder[:i]
    left_preorder = preorder[:len(left_inorder)]
    
    right_inorder = inorder[i + 1:]
    right_preorder = preorder[len(left_inorder): ]
    
    root.left = self.buildTree(left_preorder, left_inorder)
    root.right = self.buildTree(right_preorder, right_inorder)
    return root

236. Lowest Common Ancestor of a Binary Tree

My initial AC is backtracking but only beats 5%… I searched all ancestor of p and q and find their LCA, which is super low. Here’s a more concise DFS solution

1
2
3
4
5
6
7
8
9
10
11
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    if not root or root == p or root == q:
        return root
    left = self.lowestCommonAncestor(root.left, p, q)
    right = self.lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root
    if not left:
        return right
    if not right:
        return left

987. Vertical Order Traversal of a Binary Tree

Use Hashmap to log node coordinate. If in the same y level, sort it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
    from collections import defaultdict
    coordinates = defaultdict(lambda: defaultdict(list))
    res = []
    
    def searchInorder(node, x, y):
        if not node:
            return
        coordinates[x][y].append(node.val)
        searchInorder(node.left, x-1, y-1)
        searchInorder(node.right, x+1, y-1)
        return
    
    searchInorder(root, 0, 0)
    for x in sorted(coordinates.keys()):
        cur = []
        levels = coordinates[x]
        for y in sorted(levels.keys(), reverse=True):
            cur += sorted(levels[y])
        res.append(cur)
    return res

103. Binary Tree Zigzag Level Order Traversal

Classic BFS.
Odd level: left -> right
Even level: right -> left

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
    res = []
    if not root:
        return res
    q = [(root, 1)]
    while q:
        node, level = q.pop(0)
        if len(res) < level:
            res.append([])
        # odd level: left -> right
        if bool(level % 2):
            res[level - 1].append(node.val)
        else:
            res[level - 1] = [node.val] + res[level - 1] 
        if node.left:
            q.append((node.left, level + 1))
        if node.right:
            q.append((node.right, level + 1))
    return res