算法面試套路｜深度優先搜索（Depth-First Search, DFS）

本篇內容主要為 Grokking the Coding Interview: Patterns for Coding Questions 的翻譯與整理，行有餘力建議可以購買該專欄課程閱讀並在上面進行練習。

重點整理

• 深度優先搜索（Depth-First Search, DFS）
• 策略：使用 遞迴（recursion） 或透過 堆棧（stack） 追蹤遍歷過程的父節點
• 題型：
  • 樹的自根節點到葉節點遍歷
  • 樹的父子路徑相關操作

題目匯總

• 0018 Diameter of a Binary Tree
• 0020 Lowest Common Ancestor of a Binary Tree
• 0100 Same Tree
• 0104 Maximum Depth of Binary Tree
• 0110 Balanced Binary Tree
• 0111 Minimum Depth of Binary Tree
• 0112 Path Sum
• 0113 Path Sum II
• 0129 Sum Root to Leaf Numbers
• 0133 Clone Graph
• 0200 Number of Islands
• 0257 Binary Tree Paths
• 0437 Path Sum III
• 0897 Increasing Order Search Tree

[例題] Binary Tree Path Sum

問題

給定一棵二元樹（binary tree）與一個數字

$S$，找出該二元樹中是否存在一條自根節點到葉子節點的路徑，滿足路徑上節點數值總和恰好等於

$S$。

Example 01

說明	二元樹
Input : S = 10 Output : TRUE

Example 02

陣列	二元樹
Input : S = 23 Output : TRUE Input : S = 16 Output : FALSE

題解

由於我們想要 搜索自根結點到葉子節點的路徑，因此採用 深度優先搜索（Depth-First Search, DFS） 技巧。

為了遞迴遍歷二元樹，我們可以自根節點開始，呼叫兩個遞迴函數分別處理左子節點和右子節點。具體演算法的步驟如下：

1. 自根結點 root 開始進行深度優先搜索
2. 如果當前節點並不是葉子節點，進行以下操作：
   • 將路徑和減去當前節點的值，即 S = S - node.val
   • 呼叫遞迴函數，處理當前節點的左子節點和右子節點，注意子節點須滿足的路經和為前一步驟所得到的 S = S - node.val
3. 如果當前節點是葉子節點，且其值滿足路徑和
   $S$，即找到滿足條件的路徑，返回 true
4. 如果當前節點是葉子節點，但其值不滿足路徑和
   $S$ 不同，返回 talse

上述步驟如下圖所示：

1. 自根結點 root 開始進行深度優先搜索

2. 當前節點並非葉子節點，呼叫遞迴函數處理左右子節點，遞迴時 S = 23 - 12 = 11

3. 當前節點並非葉子節點，呼叫遞迴函數處理左右子節點，遞迴時 S = 11 - 7 = 4

4. 當前節點已為葉子節點，但不滿足 S = 9，故返回 false

5. 節點 7 的左子樹遞迴遍歷完畢，遍歷右子樹；由於右子樹為 null，故返回 false

6. 節點 12 的左子樹遞迴遍歷完畢，遍歷右子樹，遞迴時 S = 23 - 12 = 11

7. 當前節點並非葉子節點，呼叫遞迴函數處理左右子節點，遞迴時 S = 11 - 1 = 10

8. 當前節點已為葉子節點，並且滿足 S = 10，故返回 true

9. 左子節點滿足條件，返回 true

10. 右子節點滿足條件，返回 true

代碼

C++

class TreePathSum {
 public:
  static bool hasPath(TreeNode *root, int sum) {
    if (root == nullptr) return false;
    
    if (root->val == sum && root->left == nullptr && root->right == nullptr) return true;
    
    return hasPath(root->left, sum - root->val) || hasPath(root->right, sum - root->val);
  }
}

Java

class TreePathSum {
  public static boolean hasPaht(TreeNode root, int sum) {
    if (root == null) return false;
    
    // if the current node is a leaf and its value is equal to the sum
    if (root.val == sum && root.left == null && root.right == null) return true;
    
    // recursively call to traverse the left and right sub-tree
    return hasPath(root.left, sum - root.val) || hasPath(root.right, sum - root.val);
  }
}

JavaScript

const hasPath = (root, sum) => {
  // 邊界條件：若為空二元樹，返回 false
  if (root === null) return false;
  
  // 判斷當前節點是否為葉子節點，若為葉子節點且滿足路徑和，返回 true
  if (root.val === sum && root.left === null && root.right === null) return true;
  
  // 當前節點不滿足條件，繼續遞迴遍歷左右子節點
  return hasPath(root.left, sum - root.val) || hasPath(root.right, sum - root.val);
}

Python

def has_path(root, sum):
    if root is None:
        return False
      
    # if the current node is a leaf and its value is equal to the sum, we've found the path
    if root.val == sum and root.left is None and root.right is None:
        return True
      
    # recursively call to traverse the left and right sub-tree
    return has_path(root.left, sum - root.val) or has_path(root.right, sum - root.val)

分析

• 時間複雜度：
  $\mathcal{O}(n)$，其中
  $n$ 為二元樹中的節點總數
• 空間複雜度：
  $\mathcal{O}(n)$，該空間被用來儲存遞迴堆棧（recursion stack），最糟狀況是當給定二元樹為一個鏈表時，即所有節點都只有一個子節點

[例題] All Paths for a Sum

問題

給定一棵二元樹（binary tree）與一個數字

$S$，找出該二元樹中所有自根節點到葉子節點總和等於

$S$ 的路徑。

Example 01

說明	二元樹
Input : S = 12 Output : 2 // 1 + 7 + 4 = 12 // 1 + 9 + 2 = 12

Example 02

說明	二元樹
Input : S = 23 Output : 2 // 12 + 7 + 4 = 23 // 12 + 1 + 10 = 23

題解

這一題遵循 深度優先搜索（Depth-First Search, DFS） 策略，注意以下幾點：

• 每次找到滿足條件的路徑時，將其儲存於一個陣列中
• 我們需要遍歷所有路徑，不能在找到第一條路徑時就停止搜索

代碼

C++

class FindAllTreePaths {
 public:
  static vector<vector<int>> findPaths(TreeNode *root, int sum) {
    vector<vector<int>> allPaths;
    vector<int> currentPath;
    findPathRecursive(root, sum, currentPath, allPaths);
    return allPaths;
  }

 private:
  static void findPathsRecursive(TreeNode *currentNode, int sum, vector<int> &currentPath, vector<vector<int>> &allPaths) [
    if (currentNode == nullptr) return;
    
    currentPath.push_back(currentNode->val);
    
    if (currentNode->val == sum && currentNode->left == nullptr && currentNode->right == nullptr) {
      allPaths.push_back(vector<int>(currentPath));
    } else {
      findPathsRecursive(currentNode->left, sum - currentNode->val, currentPath, allPaths);
      findPathsRecursive(currentNode->right, sum - currentNode->val, currentPath, allPaths);
    }
    
    currentPath.pop_back();
  ]
}

Java

class FindAllTreePaths {
  public static List<List<Integer>> findPaths(TreeNode root, int sum) {
    List<List<Integer>> allPaths = new ArrayList<>();
    List<Integer> currentPath = new ArrayList<Integer>();
    
    findPathsRecursive(root, sum, currentPath, allPaths);
    return allPaths;
  }
  
  private static void findPathsRecursive(TreeNode currentNode, int sum, List<Integer> currentPath, List<List<Integer>> allPaths) {
    if (currentNode == null) return;
    
    // add the current node to the path
    currentPath.add(currentNode.val);
    
    // if current node is a leaf and its value is equal to sum, save the current path
    if (currentNode.val == sum && currentNode.left == null && currentNode.right == null) {
      allPaths.add(new ArrayList<Integer>(currentPath));
    } else {
      // traverse the left sub-tree
      findPathsRecursive(currentNode.left, sum - currentNode.val, currentPath, allPaths);
      // traverse the right sub-tree
      findPathsRecursive(currentNode.right, sum - currentNode.val, currentPath, allPaths);
    }
    
    // remove the current node from the path to backtrack
    // we need to remove the current node while we're gogin up the recursive call stack
    currentPath.remove(currentPath.size() - 1);
  }
}

JavaScript

const findPaths = (root, sum) => {
  let allPaths = [];
  findPathsRecursive(root, sum, new Deque(), allPaths);
  
  return allPaths;
}

const findPathsRecursive = (currentNode, sum, currentPath, allPaths) => {
  if (currentNode == null) return;
  
  // 添加當前節點到路徑中
  currentPath.push(currentNode.val);
  
  // 如果當前節點為葉子節點，且滿足路徑和，紀錄當前路徑
  if (currentNode.val === sum && currentNode.left === null && currentNode.right === null) {
    allPaths.push(currentPath.toArray());
  } else {
    findPathsRecursive(currentNode.left, sum - currentNode.val, currentPath, allPaths);
    findPathsRecursive(currentNode.right, sum - currentNode.val, currentPath, allPaths);
  }
  
  // 將當前節點移出路徑
  currentPath.pop();
}

Python

def find_paths(root, sum):
    all_paths = []
    find_paths_recursive(root, sum, [], all_paths)
    
    return all_paths
  
def find_paths_recursive(current_node, sum, current_path, all_paths):
    if current_node is None:
        return
      
    current_path.append(current_node.val)
    
    if current_node.val == sum and current_node.left is None and current_node.right is None:
        all_paths.append(list(current_node))
    else:
        find_paths_recursive(current_node.left, sum - current_node.val, current_path, all_paths)
        find_paths_recursive(current_node.right, sum - current_node.val, current_path, all_paths)
        
    del current_path[-1]

分析

• 時間複雜度：
  $\mathcal{O}(n\log n)$，其中
  $n$ 為二元樹中的節點總數；遍歷所有節點需要花費
  $\mathcal{O}(n)$，而在每個葉子節點，需要複製
  $\mathcal{O}(\log n)$ 個結點來儲存其路徑
• 空間複雜度：
  $\mathcal{O}(n\log n)$，其中需要
  $\mathcal{O}(n)$ 儲存遞迴堆棧（recursion stack）；而儲存所有路徑需要
  $\mathcal{O}(n\log n)$
  • 對於二元樹而言，每個葉子節點只有一條路徑可以到達，亦即路徑總數不超過葉子節點數量，因此最大元素數為
    $\mathcal{O}(\frac{n}{2})=\mathcal{O}(n)$
  • 每一條路徑包含多個節點，對於平衡二元樹來說，每個葉子節點都位在最大深度，而平衡二元樹的深度是
    $\mathcal{O}(\log n)$

[例題] Sum of Path Numbers

問題

給定一棵二元樹（binary tree），其中節點的值只可能為 0 - 9，每一條路徑代表一個數字，計算所有數字的總和。

Example 01

說明	二元樹
Output : 408 // 說明 17 + 192 + 199 = 408

Example 02

說明	二元樹
Output : 332 // 說明 101 + 116 + 115 = 332

題解

這一題遵循 深度優先搜索（Depth-First Search, DFS） 策略，在過程中需要 追蹤當前路徑表示的數字。

那麼我們要如何計算目前路徑所代表的數字呢？比如前面範例中，我們正處在 7 這個節點時，當前路徑所代表的數字為 17 = 1x10 + 7。

代碼

C++

class SumOfPathNumbers {
 public:
  static int findSumOfPathNumbers(TreeNode *root) {
    return findRootToLeafPathNumbers(root, 0);
  }

 private:
  static int findRootToLeafPathNumbers(TreeNode *root, int pathSum) {
    if (currentNode == nullptr) return 0;
    
    // calculate the path number of the current node
    pathSum = 10 * pathSum + currentNode->val;
    
    // if the current node is a leaf, return the current path sum
    if (currentNode->left == nullptr && currentNode->right == nullptr) return pathSum;
    
    // traverse the left and right sub-tree
    return findRootToLeafPathNumbers(currentNode->left, pathSum) + findRootToLeafPathNumbers(currentNode->right, pathSum);
  }
}

Java

class SumOfPathNumbers {
  public static int findSumOfPathNumbers(TreeNode root) {
    return findRootToLeafPathNumbers(root, 0);
  }
  
  private static int findRootToLeafPathNumbers(TreeNode currentNode, int pathSum) {
    if (currentNode == null) return 0;
    
    // calculate the path number of the current node
    pathSum = 10 * pathSum + currentNode.val;
    
    // if current node is a leaf, return the current path sum
    if (currentNode.left == null && currentNode.right == null) return pathSum;
    
    // traverse the left and right sub-tree
    return findRootToLeafPathNumbers(currentNode.left, pathSum) + findRootToLeafPathNumbers(currentNode.right, pathSum)
  }
}

JavaScript

const findSumOfPathNumbers = (root) => {
  return findRootToLeafPathNumbers(root, 0);
}

const findRootToLeafPathNumbers = (currentNode, pathSum) => {
  if (currentNode === null) return 0;
  
  // 計算當前節點表示的數字
  pathSum = 10 * pathSum + currentNode.val;
  
  // 如果當前節點為葉子節點，返回當前路徑數字
  if (currentNode.left === null & currentNode.right === null) return pathSum;
  
  // 遞迴遍歷左右子樹
  retrun findRootToLeafPathNumbers(currentNode.left, pathSum) + findRootToLeafPathNumbers(currentNode.right, pathSum);
}

Python

def find_sum_of_path_numbers(root):
    return find_root_to_leaf_path_numbers(root, 0)
  
def find_root_to_leaf_path_numbers(current_node, path_sum):
    if current_node is None:
        return 0
      
    # calculate the path number of the current node
    path_sum = 10 * path_sum + current_node.val
    
    # if the current node is a leaf, return the current path sum
    if current_node.left is None and current_node.right is None:
        return path_sum
      
    # traverse the left and the right sub-tree
    return find_root_to_leaf_path_numbers(current_node.left, path_sum) + find_root_to_leaf_path_numbers(current_node.right, path_sum)

分析

• 時間複雜度：
  $\mathcal{O}(n)$，其中
  $n$ 為二元樹中的節點總數
• 空間複雜度：
  $\mathcal{O}(n)$，該空間被用來儲存遞迴堆棧（recursion stack），最糟狀況是當給定二元樹為一個鏈表時，即所有節點都只有一個子節點

[例題] Path with Given Sequence

問題

給定一棵二元樹（binary tree）與一個整數陣列，判斷該整數陣列是不是樹中的一條路徑。

Example 01

說明	二元樹
Input : [1, 9, 9] Output : True

Example 02

說明	二元樹
Input : [1, 1, 6] Output : True Input : [1, 0, 7] Output : False

題解

這一題遵循 深度優先搜索（Depth-First Search, DFS） 策略，在過程中需要 判斷當前數值是否與陣列元素相符，一但不滿足可以儘早返回。

代碼

C++

class PathWithGivenSequence {
 public:
  static bool findPath(TreeNode *root, const vector<int> &sequence) {
    if (root === nullptr) return sequence.empty();
    return findPathRecursive(root, sequence, 0);
  }
  
 private:
  static bool findPathRecursive(TreeNode *currentNode, const vector<int> &sequence, int sequenceIndex) {
    if (currentNode == nullptr) return false;
    
    if (sequenceIndex >= sequence.size() || currentNode->val != sequence[sequenceIndex]) return false;
    
    if (currentNode->left == nullptr && currentNode->right == nullptr && sequenceIndex == sequence.size() - 1) return true;
    
    return findPathRecursive(currentNode->left, sequence, sequenceIndex + 1) || findPathRecursive(currentNode->right, sequence, sequenceIndex + 1);
  }
}

Java

class PathWithGivenSequence {
  public static boolean findPath(TreeNode root, int[] sequence) {
    if (root == null) return sequence.length == 0;
    return findPathRecursive(root, sequence, 0);
  }
  
  private static boolean findPathRecursive(TreeNode currentNode, int[] sequence, int sequenceIndex) {
    if (currentNode == null) return false;
    
    if (sequenceIndex >= sequence.length || currentNode.val != sequence[sequenceIndex]) retun false;
    
    if (currentNode.left == null && currentNode.right == null && sequenceIndex == sequence.length - 1) return true;
    
    return findPathRecursive(currentNode.left, sequence, sequenceIndex + 1) || findPathRecursive(currentNode.right, sequence, sequenceIndex + 1);
  }
}

JavaScript

const findPath = (root, sequence) => {
  if (root === null) return sequence.length === 0;
  
  return findPathRecursive(root, sequence, 0);
}

const findPathRecursive = (currentNode, sequence, sequenceIndex) => {
  if (currentNode === null) return false;
  
  const sequenceLength = sequence.length;
  if (sequenceIndex >= sequenceLength || currentNode.val !== sequence[sequenceIndex]) return false;
  
  if (currentNode.left === null && currentNode.right === null && sequenceIndex === sequenceLength - 1) return true;
  
  return findPathRecursive(currentNode.left, sequence, sequenceIndex + 1) || findPathRecursive(currentNode.right, sequence, sequenceIndex + 1)
}

Python

def find_path(root, sequence):
    if not root:
        return len(sequence) == 0
      
    return find_path_recursive(root, sequence, 0)
  
def find_path_recursive(current_node, sequence, sequence_index):
    if current_node is None:
        return False
      
    sequence_length = len(sequence)
    if sequence_index >= sequence_length or current_node.val != sequence[sequence_index]:
        return False
      
    if current_node.left is None and current_node.right is None and sequence_index == sequence_length - 1:
        return True
      
    return find_path_recursive(current_node.left, sequence, sequence_index + 1) or find_path_recursive(current_node.right, sequence, sequence_index + 1)

分析

• 時間複雜度：
  $\mathcal{O}(n)$，其中
  $n$ 為二元樹中的節點總數
• 空間複雜度：
  $\mathcal{O}(n)$，該空間被用來儲存遞迴堆棧（recursion stack），最糟狀況是當給定二元樹為一個鏈表時，即所有節點都只有一個子節點

[例題] Count Paths for a Sum

問題

給定一棵二元樹（binary tree）與一個數字

$S$，找出該二元樹中所有總和等於

$S$ 的路徑，注意此處的路徑並 不要求自根結點到葉子節點，只需要遵循父節點到子節點的方向即可。

Example 01

說明	二元樹
Input : S = 12 Output : 3 // 7 + 5 = 12 // 1 + 9 + 2 = 12 // 9 + 3 = 12

Example 02

說明	二元樹
Input : S = 11 Output : 2 // 7 + 4 = 11 // 1 + 10 = 11

題解

這一題遵循 深度優先搜索（Depth-First Search, DFS） 策略，注意以下幾點：

1. 必須使用一個陣列追蹤當前路徑，並傳遞給後續的遞迴函數
2. 當遍歷一個節點時，需要執行兩件事：
   • 添加當前節點到當前路徑中
   • 計算路徑陣列中以當前節點為結束元素的路徑和，若滿足
     $S$ 則將計數 count 加一
3. 必須遍歷所有路徑，不能在找到條件的路徑時就結束
4. 在返回時必須自路徑中移除當前節點，因為還必須遞迴遍歷其他路徑，需要進行回溯（backtrack）

代碼

C++

class CountAllPathSum {
 public:
  static int countPaths(TreeNode *root, int S) {
    vector<int> currentPath;
    return countPathsRecursive(root, S, currentPath);
  }
  
 private:
  static int countPathsRecursive(TreeNode *currentNode, int S, vector<int> &currentPath) {
    if (currentNode == nullptr) return 0;
    
    // add the current node to the path
    currentPath.push_back(currentNode->val);
    int pathCount = 0;
    int pathSUm = 0;
    
    // find the sum of all sub-paths in the current path
    for (vector<int>::reverse_iterator itr = currentPath.rbegin(); itr != currentPath.rend(); ++itr) {
      pathum += *itr;
      if (pathSum == S) pathCount++;
    }
    
    // traverse the left and right sub-trees
    pathCount += countPathsRecursive(currentNode->left, S, currentPath);
    pathCount += countPathsRecursive(currentNode->right, S, currentPath);
    
    // remove the current node
    currentPath.pop_back();
    
    return pathCount;
  }
}

Java

class CountAllPathSum {
  public static int countPaths(TreeNode root, int S) {
    List<Integer> currentPath = new LinkedList<>();
    return countPathsRecursive(root, S, currentPath);
  }
  
  private static int countPathsRecursive(TreeNode currentNode, int S, List<Integer> currentPath) {
    if (currentNode == null) return 0;
    
    // add current node to the path
    currentPath.add(currentNode.val);
    int pathCount = 0;
    int pathSum = 0;
    
    // find the sums of all sub-paths in the current path list
    ListIterator<Integer> pathIterator = currentPath.ListIterator(currentPath.size());
    while (pathIterator.hasPrevious()) {
      pathSum += pathIterator.previous();
      if (pathSum == S) pathCount++;
    }
    
    // traverse the left and right sub-tree
    pathCount += countPathsRecursive(currentNode.left, S, currentPath);
    pathCount += countPathsRecursive(currentNode.right, S, currentPath);
    
    // remove current node from the path to backtrack
    currentPath.remove(currentPath.size() - 1);
    
    return pathCount;
  }
}

JavaScript

const countPaths = (root, S) => {
  return countPathsRecursive(root, S, new Deque());
}

const countPathsRecursive = (currentNode, S, currentPath) => {
  if (currentNode === null) return 0;
  
  // add current node to the path
  currentPath.push(currentNode.val);
  let pathCount = 0;
  let pathSum = 0;
  
  // find the sum of all sub-paths in current path
  for (let i = currentPath.length - 1; i >= 0; i--) {
    pathSum += currentPath[i];
    if (pathSum === S) pathCount += 1;
  }
  
  // traverse left and right sub-trees
  pathCount += countPathsRecursive(currentNode.left, S, currentPath);
  pathCount += countPathsRecursive(currentNode.right, S, currentPath);
  
  // remove current node for backtracking
  currentPath.pop();
  
  return pathCount;
}

Python

def count_paths(root, S):
    return count_paths_recursive(root, S, [])
  
def count_paths_recursive(current_node, S, current_path):
    if current_node is None:
        return 0
      
    # add current node to the path
    current_path.append(current_node.val)
    path_count = 0
    path_sum = 0
    
    # find the sum of all sub-paths in current path list
    for i in range(len(current_path) - 1, -1, -1):
        path_sum += current_path[i]
        if path_sum == S:
            path_count += 1
            
    # traverse left and right sub-tree
    path_count += count_paths_recursive(current_node.left, S, current_path)
    path_count += count_paths_recursive(current_node.right, S, current_path)
    
    del current_path[-1]
    
    return path_count

分析

• 時間複雜度：遍歷所有節點需要
  $\mathcal{O}(n)$，每一個節點都必須迭代當前路徑，此時：
  • 最差狀況在傾斜樹（skewed tree）時的路徑需要
    $\mathcal{O}(n)$，故為
    $\mathcal{O}(n^2)$
  • 最優狀況在平衡樹（balanced tree）時的路徑需要
    $\mathcal{O}(\log n)$，故為
    $\mathcal{O}(n\log n)$
• 空間複雜度：
  $\mathcal{O}(n)$，該空間被用來儲存遞迴堆棧（recursion stack），最糟狀況是當給定二元樹為一個鏈表時，即所有節點都只有一個子節點；除此之外還需要有
  $\mathcal{O}(n)$ 儲存 currentPath。故
  $\mathcal{O}(n+n)=\mathcal{O}(2n)=\mathcal{O}(n)$

參考資料

• Merge Overlapping Intervals | GeeksforGeeks
• Coding Patterns: Depth First Search (DFS) | emre.me
• Depth First Search Pattern | Astik Anand