求根节点到叶节点数字之和
算法一:基于DFS
算法思路:
定义全局变量
sum
和path
dfs
传入一个节点,该节点加入path
中,并且判断该节点是否叶节点,即判断该节点的左右节点是否为NULL
(1)若为叶节点,则将path
加入到sum
中,返回
(2)若不为叶节点,则dfs
不为NULL
的左右节点
关键
不论在哪一位置在返回上一层,都需要消除当前节点对path
的影响(回溯的恢复现场)
class Solution {
public:
int sum=0;
int path=0;
int sumNumbers(TreeNode* root) {
dfs(root);
return sum;
}
void dfs(TreeNode* root){
path=path*10+root->val;
if(!root->left&&!root->right){
sum+=path;
path=(path-root->val)/10;
return;
}
if(root->left) dfs(root->left);
if(root->right) dfs(root->right);
path=(path-root->val)/10;
}
};
算法二:基于BFS
算法模板: 层序遍历
算法思路
每一次将该节点和该节点对应的数字和放入队列
出队时,判断当前节点是否为叶节点,若为叶节点,则将该节点对应的数字和加到sum
中
class Solution {
public:
int sumNumbers(TreeNode* root) {
queue<pair<TreeNode*,int>> que;
int sum=0,cur=0;
cur=root->val;
que.push({root,cur});
while(que.size()){
int n=que.size();
for(int i=0;i<n;i++){
cur=que.front().second;
TreeNode* p=que.front().first;
que.pop();
if(!p->left&&!p->right){
sum+=cur;
continue;
}
if(p->left){
int tmp=cur*10+p->left->val;
que.push({p->left,tmp});
}
if(p->right){
int tmp=cur*10+p->right->val;
que.push({p->right,tmp});
}
}
}
return sum;
}
};