描述
来源：牛客-名企高频面试题高频TOP200
给定一个二叉树的根节点root，该树的节点值都在数字 0-9 之间，每一条从根节点到叶子节点的路径都可以用一个数字表示。
找出根节点到叶子节点的所有路径表示的数字之和
例如根节点到叶子节点的一条路径是1→2→3,那么这条路径就用 123 来代替。
找出根节点到叶子节点的所有路径表示的数字之和
数据范围：节点数 0 <= n <= 100，保证结果在32位整型范围内
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n^2)
进阶：空间复杂度 O(n)O(n)，时间复杂度 O(n)
答案及解析
DFS, 解决方式就是从根节点往下走的时候，那么当前节点的值就是父节点的值*10+当前节点的值。默认根节点的父节点的值是0，如果到达叶子结点，就用一个全局的变量把叶子结点的值加起来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| vector<int> vec;
int total = 0;
void GetSum(TreeNode* root,vector<int>& vec)
{
if(!root)
return;
vec.push_back(root->val);
if(!root->left && !root->right)
{
int sum = 0;
for(auto i : vec)
{
sum *= 10;
sum += i;
}
total += sum;
}
if(root->left)
{
GetSum(root->left,vec);
vec.pop_back();
}
if(root->right)
{
GetSum(root->right,vec);
vec.pop_back();
}
return;
}
int sumNumbers(TreeNode* root) {
if(root == NULL)
return 0;
vec.clear();
GetSum(root, vec);
return total;
}
|
时间复杂度：O(N), 为二叉树节点数
空间复杂度：O(N), 使用一个数组
