【試題描述】

???? 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.

???? 輸入一個整數(shù)和一棵二元樹。從樹的任意結點開始往下訪問所經過的所有結點形成一條路徑。

打印出和與輸入整數(shù)相等的所有路徑。

?

解題思路：

?

????? 一層一層的遍歷，保存當前節(jié)點到根節(jié)點的完整路徑，然后從當前節(jié)點向上掃描，如果找到了當前節(jié)點到某個節(jié)點的和等于給定值，則輸出之。程序對每個節(jié)點都需要遍歷一遍，還要掃描當前節(jié)點到根節(jié)點的路徑，且需要保存每個節(jié)點到根節(jié)點的路徑，所以時間復雜度為O（nlgn)，空間復雜度為O(nlgn)。

1 public static void findAllPath(Node head, int sum, ArrayList<Integer> buffer, int level) 2 { 3 if (head == null) 4 return; 5 int tmp = sum; 6 buffer.add(head.value); 7 for (int i = level; i >= 0; i--) 8 { 9 tmp -= buffer.get(i); 10 if (tmp == 0) 11 print(buffer, i, level); 12 } 13 14 ArrayList<Integer> c1 = (ArrayList<Integer>) buffer.clone(); 15 ArrayList<Integer> c2 = (ArrayList<Integer>) buffer.clone(); 16 17 findAllPath(head.left, sum, c1, level + 1); 18 findAllPath(head.right, sum, c2, level + 1); 19 } 20 21 private static void print(ArrayList<Integer> buffer, int level, int i2) 22 { 23 System.out.print("找到路徑為："); 24 for (int i = level; i <= i2; i++) 25 System.out.print(buffer.get(i) + " "); 26 System.out.println(); 27 28 }

?

?

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

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

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