目錄
- 1、題目
- 2、思路
- 3、c++代碼
- 4、java代碼
1、題目
給你一個二叉樹的根節點 root，樹中每個節點都存放有一個 0 到 9 之間的數字，
每條從根節點到葉節點的路徑都代表一個數字：
- 例如，從根節點到葉節點的路徑
1 -> 2 -> 3表示數字123，
計算從根節點到葉節點生成的 所有數字之和 ，
葉節點 是指沒有子節點的節點，
示例 1：
輸入：root = [1,2,3]
輸出：25
解釋：
從根到葉子節點路徑 1->2 代表數字 12
從根到葉子節點路徑 1->3 代表數字 13
因此，數字總和 = 12 + 13 = 25
示例 2：
輸入：root = [4,9,0,5,1]
輸出：1026
解釋：
從根到葉子節點路徑 4->9->5 代表數字 495
從根到葉子節點路徑 4->9->1 代表數字 491
從根到葉子節點路徑 4->0 代表數字 40
因此，數字總和 = 495 + 491 + 40 = 1026
提示：
- 樹中節點的數目在范圍
[1, 1000]內 0 <= Node.val <= 9- 樹的深度不超過
10
2、思路
(dfs,樹的遍歷) O ( n ) O(n) O(n)
從根節點遞回遍歷整棵樹，遍歷時維護從根節點到該節點路徑表示的數，當遍歷到葉節點時，將路徑表示的數累加到答案中，
遞回函式設計：
void dfs(TreeNode* root, int number)
root是當前遍歷的節點，number是從根節點到當前節點路徑表示的數，
遞回邊界：
- 遍歷到葉節點時，將根節點到當前葉節點路徑維護的數字加入答案中，
遞回程序如下：
- 1、從根節點開始往下遍歷，維護一個從根節點到當前節點路徑表示的數
number，初始值為0， - 2、遍歷當前節點
root，將root->val追加到number中，即執行number = number * 10 + root->val操作， - 3、如果左子樹不為空，遞回到左子樹，如果右子樹不為空，遞回到右子樹，
- 4、當遍歷到葉節點時，將
number加入到數字之和res中， - 5、最后回傳
res，
時間復雜度分析： O ( n ) O(n) O(n)，其中 n n n是二叉樹的節點個數，對每個節點訪問一次，
3、c++代碼
class Solution {
public:
int res = 0;
int sumNumbers(TreeNode* root) {
dfs(root, 0);
return res;
}
void dfs(TreeNode* root, int number)
{
number = number * 10 + root->val;
if(!root->left && !root->right) res += number; //遍歷到葉節點，將number加入res中
if(root->left) dfs(root->left,number); //遞回左子樹
if(root->right) dfs(root->right,number); //遞回右子樹
}
};
4、java代碼
class Solution {
int res = 0;
public int sumNumbers(TreeNode root) {
dfs(root, 0);
return res;
}
public void dfs(TreeNode root, int number)
{
number = number * 10 + root.val;
if(root.left == null && root.right == null) res += number; //遍歷到葉節點，將number加入res中
if(root.left != null) dfs(root.left,number); //遞回左子樹
if(root.right != null) dfs(root.right,number); //遞回右子樹
}
}
原題鏈接： 129. 求根節點到葉節點數字之和
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/293954.html
標籤：java