DFS summary
Scenes
- Permutations
-
Find out all the cases
Tree DFS
104 Maxmum depth of binary tree
- if not root: 0; left_d=dfs(root.left); right_d=dfs(root.right);return max(left_d, right_d) + 1
- Time: O(N)
- DFS Space:O(height), BFS Space: worest case O(n)
543. Diameter of Binary Tree
- Glouble variable: self.d
- dfs(root) for the subtree longest depth: if not root: 0; left_d=dfs(root.left); right_d=dfs(root.right); self.d = max(self.d, left_d +right_d); return max(left_d, right_d) + 1
- return self.d
- Time: O(n),
- Space: O(height) (stack, recurse)
class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: self.res = 0 def dfs(node): if not node: return 0 left_d = dfs(node.left) right_d = dfs(node.right) self.res = max(self.res, left_d + right_d) return max(left_d, right_d) +1 dfs(root) return self.res
124. Binary Tree Maximum Path Sum
- self.res = float(“-inf”)
- def max_sum_oneside(node):return max(0, max(left_s, right_s) + node.val)
- self.res = max(self.res, left_s + right_s + node.val)
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
self.res = float("-inf")
def max_sum_oneside(node):
if not node:
return 0
left_s = max_sum_oneside(node.left)
right_s = max_sum_oneside(node.right)
self.res = max(self.res, left_s + right_s + node.val)
return max(0, max(left_s, right_s) + node.val)
max_sum_oneside(root)
return self.res
94 binary tree inorder traversal
- time: O(n), space: O(height)
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def dfs(node):
if not node:
return
dfs(node.left)
res.append(node.val)
dfs(node.right)
dfs(root)
return res
110. Balanced Binary Tree
- the same method as 104 for depth -> diff depth
- abs(height_diff) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)