Depth-First Search

Tree O(n \* m) Link to heading

Traverse by Orders Link to heading

dfs(root) {
    // preorder
    dfs(root.left)
    // inorder
    dfs(root.right)
    // postorder
}

     1
   /   \
  2     3
 / \   / \
4   5 6   7

• Preorder traversal: root, left, right: 1245367
• Inorder traversal: left root right: 4251637
• Postorder traversal: left, right, root: 4526731
• 大部分时候是 void inorder(), preorder(), postorder()

基于 Traverse Orders, 更实用的 useage Link to heading

dfs(res, root, value) {
    if (!root):
        return

    if (value = root.val):
        res.add(root)
        return

    for option : options:
        做选择
        dfs(res, newRoot, newValue)
        撤销选择
}

• 步骤

  1. base case: if root == null
  2. inductive case: if can make recursive call
  3. return

• Helper functions

  • depth(), isBST(), nodeCount(), dfs()
  • 讲究 order 时 (一般用 PostOrder 方式)
    • dfs() return TreeNode
    • 根据 returned left & right 判断

其他不同的格式 O(2^N) 每个元素用一次, 每个元素只有两种选择 Link to heading

逻辑相似 (e.g. Permutation - 找到所有可能性) Link to heading

• helper function 必不可少

  • dfs(所有选项, 当前 index, res, cur)

• index 注意:

  • base case & recursive call 中的 index 判定: Value | Index

• 步骤

  1. base case: index 或者 cur 达到上限
  2. inductive:
  • recursive call with new index & cur
    • cur.add() + dfs(...) + cur.remove()
  • 如果是更改 input, 需要快慢指针 swap 来代替 cur 和 res
  • dfs()/main()中可以加 set 来防重
    • 取决于题型: 前后 add + remove, 或者设定 true / false
    • 取决于题型: set 保存 value 还是 index

• 防重

  // 1. 如果Traverse strategy每次从index开始, 必须要sort
  Arrays.sort(num)
  
  // 2. 当前**traverse**中, 不能重复使用某元素
  if (visitedIndex.contains(i)) {
      continue;
  }
  
  // 3. 当前**level**中, 不能以相同数值做起点 (用nums[i] == nums[i-1]代替set)
  Set<Integer> visitedValue = new HashSet<>();
  for (i from x to y) {
    if (visitedValue.contains(nums[i])) {
        continue;
    }
  
    visitedValue.add(nums[i]);
  }