题目

题解

二叉树结构如下：

//Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

1.递归法

class Solution {
public:
    int sumNumbers(TreeNode* root) {//两种方法。1.递归法
        return DFSsunNumbers(root,0);//调用递归程序
    }

    int DFSsunNumbers(TreeNode* root, int sum){
        if(!root) return 0;//root为空直接返回
        sum = sum*10 + root->val;//进行加法，记得×10
        if(!root->left && !root->right) return sum;//遇到叶节点就返回
        return DFSsunNumbers(root->left,sum)+DFSsunNumbers(root->right,sum);//递归左右子树并相加
    }
};

2.双栈迭代法

 //和#112类似
class Solution {
public:
    int sumNumbers(TreeNode* root) {//两种方法。2.迭代法
//用两个栈分别保存该路径节点和当前路径的和
//也可以直接修改二叉树上的值，但会改变原始数据
        if(!root) return 0;//特殊情况
        int res = 0, currentSum = 0;//初始化结果和当前路径和
        stack<TreeNode*> s{{root}};
        stack<int> sNum{{0}};//定义两个栈
        while(!s.empty()){//s不为空继续迭代
            TreeNode* tmp = s.top();s.pop();//取栈s顶的值
            int currentSum = sNum.top()*10+tmp->val;sNum.pop();//取sNum栈顶的值*10加上当前节点的值
            if(!tmp->left && !tmp->right){
                res += currentSum;
            }//若为叶节点，res加上该currentSum
            if(tmp->left){
                s.push(tmp->left);
                sNum.push(currentSum);
            } //若左子树存在，则两个栈分别压入节点和当前路径值
            if(tmp->right){
                s.push(tmp->right);
                sNum.push(currentSum);
            }//同上
        }
        return res;
    }
};