|
If you wish to survive you need to cultivate a strong mental attitude.
如果你想活著,，需要培養(yǎng)一顆堅強(qiáng)的心,。 給定一個二叉樹，它的每個結(jié)點都存放一個 0-9 的數(shù)字,，每條從根到葉子節(jié)點的路徑都代表一個數(shù)字,。 例如，從根到葉子節(jié)點路徑 1->2->3 代表數(shù)字 123,。 計算從根到葉子節(jié)點生成的所有數(shù)字之和,。 說明: 葉子節(jié)點是指沒有子節(jié)點的節(jié)點。 示例 1: 輸入: [1,2,3] 1 / \ 2 3 輸出: 25 解釋: 從根到葉子節(jié)點路徑 1->2 代表數(shù)字 12. 從根到葉子節(jié)點路徑 1->3 代表數(shù)字 13. 因此,，數(shù)字總和 = 12 + 13 = 25.
示例 2: 輸入: [4,9,0,5,1] 4 / \ 9 0 / \ 5 1 輸出: 1026 解釋: 從根到葉子節(jié)點路徑 4->9->5 代表數(shù)字 495. 從根到葉子節(jié)點路徑 4->9->1 代表數(shù)字 491. 從根到葉子節(jié)點路徑 4->0 代表數(shù)字 40. 因此,，數(shù)字總和 = 495 + 491 + 40 = 1026.
這題說的是每條從根節(jié)點到葉子結(jié)點的路徑都代表一個數(shù)字，然后再把這些數(shù)字加起來即可,。遍歷一棵樹從根節(jié)點到葉子結(jié)點的所有路徑,，最容易想到的是DFS，所以這題使用DFS是最容易解決的,。如果對二叉樹的DFS不熟悉的話,，可以看下373，數(shù)據(jù)結(jié)構(gòu)-6,樹
解決方式就是從根節(jié)點往下走的時候,，那么當(dāng)前節(jié)點的值就是父節(jié)點的值*10+當(dāng)前節(jié)點的值,。默認(rèn)根節(jié)點的父節(jié)點的值是0，如果到達(dá)葉子結(jié)點,，就用一個全局的變量把葉子結(jié)點的值加起來,。這里就以示例2為例來畫個圖看一下
搞懂了上的分析過程，代碼就容易多了
1public int sumNumbers(TreeNode root) {
2 //如果根節(jié)點是空,，直接返回0即可
3 if (root == null)
4 return 0;
5 //兩個棧,，一個存儲的是節(jié)點，一個存儲的是節(jié)點對應(yīng)的值
6 Stack<TreeNode> nodeStack = new Stack<>();
7 Stack<Integer> valueStack = new Stack<>();
8 //全局的,，統(tǒng)計所有路徑的和
9 int res = 0;
10 nodeStack.add(root);
11 valueStack.add(root.val);
12 while (!nodeStack.isEmpty()) {
13 //當(dāng)前節(jié)點和當(dāng)前節(jié)點的值同時出棧
14 TreeNode node = nodeStack.pop();
15 int value = valueStack.pop();
16 if (node.left == null && node.right == null) {
17 //如果當(dāng)前節(jié)點是葉子結(jié)點,，說明找到了一條路徑，把這條
18 //路徑的值加入到全局變量res中
19 res += value;
20 } else {
21 //如果不是葉子節(jié)點就執(zhí)行下面的操作
22 if (node.right != null) {
23 //把子節(jié)點和子節(jié)點的值分別加入到棧中,，這里子節(jié)點的值
24 //就是父節(jié)點的值*10+當(dāng)前節(jié)點的值
25 nodeStack.push(node.right);
26 valueStack.push(value * 10 + node.right.val);
27 }
28 if (node.left != null) {
29 nodeStack.push(node.left);
30 valueStack.push(value * 10 + node.left.val);
31 }
32 }
33 }
34 return res;
35}
如果嫌上面代碼多,，也可以改為遞歸的方式 1public int sumNumbers(TreeNode root) {
2 return dfs(root, 0);
3}
4
5private int dfs(TreeNode root, int sum) {
6 //終止條件的判斷
7 if (root == null)
8 return 0;
9 //計算當(dāng)前節(jié)點的值
10 sum = sum * 10 + root.val;
11 //如果當(dāng)前節(jié)點是葉子節(jié)點，說明找到了一條完整路徑,，直接
12 //返回這條路徑的值即可
13 if (root.left == null && root.right == null)
14 return sum;
15 //如果當(dāng)前節(jié)點不是葉子結(jié)點,，返回左右子節(jié)點的路徑和
16 return dfs(root.left, sum) + dfs(root.right, sum);
17}
原理和上面DFS類似,，每遍歷一個結(jié)點,，我們就要重新計算當(dāng)前節(jié)點的值，那么當(dāng)前節(jié)點的值就是父節(jié)點的值*10+當(dāng)前節(jié)點的值,。
1public int sumNumbers(TreeNode root) {
2 //邊界條件的判斷
3 if (root == null)
4 return 0;
5 Queue<TreeNode> nodeQueue = new LinkedList<>();
6 Queue<Integer> valueQueue = new LinkedList<>();
7 int res = 0;
8 nodeQueue.add(root);
9 valueQueue.add(root.val);
10 while (!nodeQueue.isEmpty()) {
11 //節(jié)點和節(jié)點對應(yīng)的值同時出隊
12 TreeNode node = nodeQueue.poll();
13 int value = valueQueue.poll();
14 if (node.left == null && node.right == null) {
15 //如果當(dāng)前節(jié)點是葉子結(jié)點,，說明找到了一條路徑，把這條
16 //路徑的值加入到全局變量res中
17 res += value;
18 } else {
19 //如果不是葉子節(jié)點就執(zhí)行下面的操作
20 if (node.left != null) {
21 //把子節(jié)點和子節(jié)點的值分別加入到隊列中,，這里子節(jié)點的值
22 //就是父節(jié)點的值*10+當(dāng)前節(jié)點的值
23 nodeQueue.add(node.left);
24 valueQueue.add(value * 10 + node.left.val);
25 }
26 if (node.right != null) {
27 nodeQueue.add(node.right);
28 valueQueue.add(value * 10 + node.right.val);
29 }
30 }
31 }
32 return res;
33}
這題從根節(jié)點到每個葉子結(jié)點都是一個完整的數(shù)字，我們要做的就是把這每個數(shù)字加起來,。使用DFS應(yīng)該是最容易理解的,，其實每條路徑也可以把它想象成為一個鏈表，每個鏈表代表一個數(shù)字,，然后把所有的鏈表所代表的數(shù)字加起來就是這題要求的結(jié)果,。
|
