?

【試題描述】

?

輸入一個整數和一棵二元樹。從樹的根結點開始往下訪問一直到葉結點所經過的所有結點形成一條
路徑。打印出和與輸入整數相等的所有路徑。
例如輸入整數 22 和如下二元樹
? ? ? ? ? ? ? ? ? ? 10
? ? ? ? ? ? ? ? ? ?/ ? ?\
? ? ? ? ? ? ? ? ?5 ? ? ?12

? ? ? ? ? ? ? ?/ ? ?\?
? ? ? ? ? ? ?4 ? ? ?7
則打印出兩條路徑:10, 12 和 10, 5, 7。

據說這是百度的一道筆試題。

?

分析：這道題考查對二叉樹遍歷方式的理解，采用后序遍歷，如果把二叉樹看成圖，就是圖的深度遍歷。使用變量存放當前遍歷的路徑和，當訪問到某一結點時，把該結點添加到路徑上，并累加當前結點的值。如果當前結點為葉結點并且當前路徑的和剛好等于輸入的整數，則當前的路徑符合要求，我們把它打印出來。如果當前結點不是葉結點，則繼續訪問它的子結點。當前結點訪問結束后，遞歸函數將自動回到父結點，因此我們在函數退出之前要在路徑上刪除當前結點并減去當前結點的值，以確保返回父結點時路徑剛好是根結點到父結點的路徑。

?

【參考代碼】

1 public static void findPath(Node root, int sum, int curSum, LinkedList path) 2 { 3 if (root == null) 4 return; 5 curSum += root.value; 6 path.add(root.value); 7 8 // if the node is a leaf, and the sum is same as pre-defined, 9 // the path is what we want. print the path 10 if (root.left == null && root.right == null && curSum == sum) 11 { 12 System.out.println("Find a path: "); 13 Iterator it = path.iterator(); 14 while (it.hasNext()) 15 { 16 System.out.print(it.next() + " ");// 打印路徑節點的值 17 } 18 System.out.println(); 19 } 20 21 // if the node is not a leaf, goto its children 22 if (root.left != null) 23 findPath(root.left, sum, curSum, path); 24 if (root.right != null) 25 findPath(root.right, sum, curSum, path); 26 27 // when we finish visiting a node and return to its parent node, 28 // we should delete this node from the path and 29 // minus the node's value from the current sum 30 curSum -= root.value; 31 path.pollLast(); 32 }

?

?

?

總結

以上是生活随笔為你收集整理的【IT笔试面试题整理】二叉树中和为某一值的路径--从根到叶子节点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。