Tree Depth-First Search

Posted on

重点掌握左右子树相关和不相关时，两种递归代码的写法。

This pattern is based on the Depth-First Search (DFS) technique to traverse a tree.

We will be using recursion (or we can also use a stack for the iterative approach) to keep track of all the previous (parent) nodes while traversing. This also means that the space complexity of the algorithm will be O(H), where “H” is the maximum height of the tree.

Snippets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
"""L&R Unrelated"""
def dfs(root, path):
    if not root:
        return
    
    path = path + [root.val]
    if not root.left and not root.right and sum(path) == targetSum:
        ans.append(path)
    
    dfs(root.left, path)
    dfs(root.right, path)

ans = []
dfs(root, [])

return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
"""L&R Related"""
def dfs(root):
    if not root:
        return 0
    
    l = max(0, dfs(root.left))
    r = max(0, dfs(root.right))

    nonlocal ans
    ans = max(ans, l + r + root.val)

    return max(l, r) + root.val

ans = root.val
dfs(root)

return ans

LeetCode

112. Path Sum
113. Path Sum II
129. Sum Root to Leaf Numbers
1430. Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree
437. Path Sum III
543. Diameter of Binary Tree
124. Binary Tree Maximum Path Sum