面試題中的二叉樹根據和尋路徑問題

二叉樹是面試裡常考的一類數據結構，其中有一類尋找路徑問題很有意思。目前見過兩種類型題目，都是先給出一個和，然後要求打印出節點值之和與此相等的路徑問題。

1. Given a binary tree and a number, print all the root-to-leaf paths such that adding up all the values along the path equals the given number.

這個題目比較簡單，因為要求所求的路徑必須從根節點到葉節點。注意這裡所說的二叉樹並不是二叉搜索樹。此外，如果面試時遇到這個題目，首先應該問面試官確定二叉樹的節點值是否都是正數。如果有全為正數這個限制，那麼設計的算法可以有效進行剪枝——如果當前路徑的和已經超過了目標和，則可以停止繼續搜索了。

搜索時記錄當前路徑上的所求節點以及當前和。

搜索分為兩種情況：

1）遇到葉節點：檢查是否路徑的和與目標和相等，若相等則為所求；

2）遇到非葉節點：對左右兩個分支遞歸調用搜索函數。

 @SuppressWarnings("unchecked")
 public static void findPaths(TreeNode root, int sum, int curSum,
   ArrayList<Integer> path, ArrayList<ArrayList<Integer>> paths) {
  if (root == null)
   return;

  path.add(root.val);
  curSum += root.val;
  // leaf node
  if (root.left == null && root.right == null) {
   if (curSum == sum) {
    paths.add(path);
   }
  }
  // non-leaf node
  else {
   findPaths(root.left, sum, curSum, (ArrayList<Integer>) path.clone(),
      paths);

   findPaths(root.right, sum, curSum, path, paths);
  }
 }

 public static void main(String args[]) {
  TreeNode root = new TreeNode(10);
  root.left = new TreeNode(8);
  root.right = new TreeNode(2);
  root.left.left = new TreeNode(3);
  root.left.right = new TreeNode(5);
  root.right.left = new TreeNode(2);

  ArrayList<Integer> path = new ArrayList<Integer>();
  ArrayList<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();

  findPaths(root, 21, 0, path, paths);
  System.out.println(paths);

  path.clear();
  paths.clear();
  findPaths(root, 23, 0, path, paths);
  System.out.println(paths);

  path.clear();
  paths.clear();
  findPaths(root, 14, 0, path, paths);
  System.out.println(paths);
 }

為了使得這裡的算法能夠有較好的適用性，這裡假設沒有全為正數這個條件，而且希望能夠把所有路徑都收集起來，而不是遇到一條所求路徑就打印出來。我這裡將所有的所求路徑都放到了一個二維數組鏈表容器裡。

注意這裡遞歸調用時我對path使用了clone函數，表明是傳值而非傳引用。本質是利用了回溯的思想，保證即使路徑沒有找到，path最終不會被修改而影響同一個函數內的下一次遞歸調用。時間復雜度是O(N*logN)，因為每個節點遍歷了一遍用了O(N)時間，而對於每個節點，傳遞path或者說打印path都需要O(logN)時間。

2. You are given a binary tree in which each node contains a value Design an algorithm to print all paths which sum up to that value Note that it can be any path in the tree

- it does not have to start at the root.

這裡仍然假設並不全為正數。不過這題有個地方說法可能不夠嚴謹：對於任意的路徑，是否允許兩條自上而下的路徑在最高處相交而和合成的一條路徑的情況？例如，對於一個僅有3個節點的二叉樹，根節點有左右兩個孩子節點，那麼從左孩子節點到右孩子節點的倒V字型路徑到底算不算？顯然，如果這樣的路徑也需要考慮的話，情況會更加復雜。不過我見過的題目裡沒有考慮到這種情況的。

這題仍然沿著上題的思路進行擴展即可，遇到任意一個節點：
1）延續當前路徑和繼續增加當前和；
2）從左右孩子節點開始一條新路徑，並且將當前和清零。

 @SuppressWarnings("unchecked")
 public static void findPaths(TreeNode node, int sum, int curSum,
   ArrayList<Integer> path, ArrayList<ArrayList<Integer>> paths) {
  if (node == null) {
   return;
  }

  path.add(node.val);
  curSum += node.val;

  // the path can end with the current node
  if (sum == curSum) {
   paths.add(path);
  }

  // continue the current path, or start another path from the next node
  if (node.left != null) {
   // continue the current path
   findPaths(node.left, sum, curSum,
     (ArrayList<Integer>) path.clone(), paths);
   // start another new path from the left child node
   findPaths(node.left, sum, 0, new ArrayList<Integer>(), paths);
  }
  if (node.right != null) {
   // continue the current path
   findPaths(node.right, sum, curSum,
     (ArrayList<Integer>) path.clone(), paths);
   // start another new path from the right child node
   findPaths(node.right, sum, 0, new ArrayList<Integer>(), paths);
  }
 }

不過測試時發現這裡存在重復遞歸，從而生成了冗余的路徑。原因是我在進行對當前路徑擴展的遞歸調用和生成新路徑的遞歸調用使用的同一個函數接口。舉個例子說明，假設輸入的二叉樹至少有3層，在根節點搜索時，會產生兩個搜索分支：

1.1）嘗試讓子節點延續以根節點為起點的路徑；

1.2）嘗試以子節點為起點的新路徑。

而在子節點搜索時，對於分支1.1，會再產生兩個搜索分支：

2.1）嘗試讓孫子節點延續以根節點為起點的路徑；

2.2）嘗試以孫子節點為起點的新路徑。

對於分支1.2，也會產生兩個搜索分支：

2.3) 嘗試讓孫子節點延續以父節點為起點的路徑；

2.4) 嘗試以孫子節點為起點的新路徑。

可以發現，分支2.2和2.4完全相同，屬於重復遞歸。解決的方法是使用兩個不同的搜索函數：一個負責搜索所有可能路徑，另一個只負責通過延續當前路徑來搜索。

 public static void findPaths(TreeNode node, int sum,
   ArrayList<Integer> path, ArrayList<ArrayList<Integer>> paths) {
  if (node == null) {
   return;
  }

  // continue the current path
  continueCurPath(node, sum, 0, path, paths);

  // start a new path from the next node
  findPaths(node.left, sum, new ArrayList<Integer>(), paths);
  findPaths(node.right, sum, new ArrayList<Integer>(), paths);
 }

 @SuppressWarnings("unchecked")
 public static void continueCurPath(TreeNode node, int sum, int curSum,
   ArrayList<Integer> path, ArrayList<ArrayList<Integer>> paths) {
  if (node == null) {
   return;
  }

  curSum += node.val;
  path.add(node.val);

  if (curSum == sum) {
   paths.add(path);
  }

  continueCurPath(node.left, sum, curSum,
    (ArrayList<Integer>) path.clone(), paths);
  continueCurPath(node.right, sum, curSum,
    (ArrayList<Integer>) path.clone(), paths);
 }

 public static void main(String args[]) {
  TreeNode root = new TreeNode(10);
  root.left = new TreeNode(8);
  root.right = new TreeNode(2);
  root.left.left = new TreeNode(3);
  root.left.right = new TreeNode(5);
  root.right.left = new TreeNode(2);
  root.left.right.left = new TreeNode(5);

  ArrayList<Integer> path = new ArrayList<Integer>();
  ArrayList<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();

  findPaths(root, 21, path, paths);
  System.out.println(paths);

  path.clear();
  paths.clear();
  findPaths(root, 23, path, paths);
  System.out.println(paths);

  path.clear();
  paths.clear();
  findPaths(root, 14, path, paths);
  System.out.println(paths);

  path.clear();
  paths.clear();
  findPaths(root, 5, path, paths);
  System.out.println(paths);
 }
}

以上代碼中當輸入的目標和為5時，僅僅返回兩條路徑。算法復雜度的分析和第一題一樣，仍然是O(N*logN)。