Algorithm-DFS

DFS summary

def dfs(curr):
  visited.add(curr)
  for next in curr.neighbors:
    if next not in visited:
      dfs(next)

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)