二叉树根节点到叶子节点的所有路径和

我觉得这个题目和剑指offer中的一道题目非常相似。先说这个题：
解题思路：从根结点开始，当每访问到一个结点，我们把该结点添加到路径上，并"累加"
该结点的值，这里"累加"的含义指的是按照题目的要求组成相应的数字即"左移"后相加。
如果该结点为叶结点，那么一条路径搜索完成，将当前所得结果累加。如果当前不是叶子
结点，则继续访问它 的子结点。当前结点访问结束后，递归函数将自动回到它的父结点。
因此我们在函数退出之前要在路径上"删除"当前结点，做法就是将当前路径值/10，以确
保返回父结点时路径刚好是从根结点到父结点的路径。我们不难看出保存路径的数据结构
实际上是一个栈，因为路径要与递归调用状态一致，而递归调用的本质就是一个压栈和出
栈的过程。
class Solution {
public:
    void sumNumbersCore(TreeNode *root, int &pathNum, int &sum) {
        if(root){
            pathNum = pathNum * 10 + root->val;
            //如果是叶子节点，一条路径搜索完成，累加到sum
            if(!root->left && !root->right){
                sum += pathNum;               
            }
            //如果不是叶子节点，则遍历它的子结点
            else{
                if(root->left)
                    sumNumbersCore(root->left, pathNum, sum);
                if(root->right)
                    sumNumbersCore(root->right, pathNum, sum);
            }
            //返回父结点之前，路径上“删除”当前节点
            pathNum /= 10;                     
        }
    }
    
    int sumNumbers(TreeNode *root) {
        int pathNum = 0;
        int sum = 0;
        sumNumbersCore(root, pathNum, sum);
        return sum;
    }
};

剑指offer面试题25：输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入
整数的所有路径。从树的根结点开始往下一直到叶节点所经过的结点形成一条路径。
解题思路：从根结点开始，当每访问到一个结点，我们把该结点添加到路径上，并累加
该结点的值。如果该结点为叶结点并且路径中结点值的和刚好等于输入的整数，则当前
路径符合要求，我们把它打印出来。如果当前不是叶子结点，则继续访问它的子结点。
当前结点访问结束后，递归函数将自动回到它的父结点。因此我们在函数退出之前要在
路径上删除当前结点并减去当前结点的值，以确保返回父结点时路径刚好是从根结点到
父结点的路径。我们不难看出保存路径的数据结构实际上是一个栈，因为路径要与递归
调用状态一致，而递归调用的本质就是一个压栈和出栈的过程。
class Solution {
public:
    void hasPathSumCore(TreeNode *root, int &currentSum, int target, bool &flag){
        if(root){
            currentSum += root->val;
            //如果当前结点是叶子节点并且路径上结点的和等于target
            if(!root->left && !root->right){
                if(currentSum == target)
                    flag = true;
            }
            //如果不是叶子结点，则遍历它的子结点
            else{
                if(root->left)
                    hasPathSumCore(root->left, currentSum, target, flag);
                if(root->right)
                    hasPathSumCore(root->right, currentSum, target, flag);
            }
            //返回父结点之前，在路径上删除当前结点
            currentSum -= root->val;
        }
    }
    
    bool hasPathSum(TreeNode *root, int sum) {
        int currentSum = 0;
        bool flag = false;
        hasPathSumCore(root, currentSum, sum, flag);
        return flag;
    }
};

如果我们要求的再严格一些，输出二叉树中和为某一值的路径，其实可以用同一种思路
去解，可以沿用上面的代码，只需略作修改：
class Solution {
public:
    void hasPathSumCore(TreeNode *root, int &currentSum, int target,  vector<int> &tempPath, vector<vector<int>> &paths){
        if(root){
            tempPath.push_back(root->val);
            currentSum += root->val;
            //如果是叶子结点，并且路径和等于target，保存当前路径
            if(!root->left && !root->right){
                if(currentSum == target)
                    paths.push_back(tempPath);               
            }
            //如果不是叶子结点，遍历其子结点
            else{
                if(root->left)
                    hasPathSumCore(root->left,currentSum,target,tempPath,paths);
                if(root->right)
                    hasPathSumCore(root->right,currentSum,target,tempPath,paths);
            }
            //返回到父结点之前，在路径上pop_back()当前节点，
            //相应的在路径和中减去当前节点的val。
            currentSum -= root->val;
            tempPath.pop_back();
        }
    }
    
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        int currentSum = 0;
        vector<vector<int>> paths;
        vector<int> tempPath;
        hasPathSumCore(root, currentSum, sum, tempPath, paths);
        return paths;
    }
};

//根据BFS找到所有叶子节点到根节点的路径，然后相加
class Solution {
public:
     int sumNumbers(TreeNode *root) {
        if (root == nullptr)
            return 0;
        int sum = 0;
        //用BFS实现
        unordered_map<TreeNode*,TreeNode*> path;
        path[root] = root;
        //保存叶节点
        vector<TreeNode*> leafNode;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()){
            TreeNode* temp = q.front();
            q.pop();
            if (temp->left != nullptr){
                path[temp->left] = temp;
                q.push(temp->left);
            }
            if (temp->right != nullptr){
                path[temp->right] = temp;
                q.push(temp->right);
            }
            if (temp->left == nullptr && temp->right == nullptr)
                leafNode.push_back(temp);
        }
        //开始找每一个叶子节点到根节点的路径的节点值
        for (auto node : leafNode){
            int sumTemp = 0;
            //代表位数
            int i = 1;
            while (node != root){
                sumTemp += node->val * i;
                node = path[node];
                i *= 10;
            }
            sumTemp += root->val*i;
            sum += sumTemp;
        }
        return sum;
    }
};

• 使用stack+dfs的思想，感觉比一般的树遍历思路清晰一些

  class Solution_129 {
  public:
    int sumNumbers(TreeNode *root) {
        if (!root)
        {
            return 0;
        }
        stack sta;
        sta.push(root);
        int ret = 0;
        TreeNode* top = 0;
        while (!sta.empty())
        {
            top = sta.top();
            sta.pop();
            if (!top->left && !top->right)
            {
                ret += top->val;
            }
            if (top->left)
            {
                top->left->val += 10 * top->val;
                sta.push(top->left);
            }
            if (top->right)
            {
                top->right->val += 10 * top->val;
                sta.push(top->right);
            }
        }
        return ret;
    }
  };
  

class Solution(object):
    def sumNumbers(self, root, prefix=0):
        if root == None:
            return 0
        prefix = prefix * 10 + root.val
        if root.left == None and root.right == None:
            return prefix
        return self.sumNumbers(root.left, prefix) + self.sumNumbers(root.right, prefix)

package leetcode.tree;

public class Sumroottoleafnumbers {
	
	private String str = new String();
	private int sum = 0;
	
    public int sumNumbers(TreeNode root) {
    	if (root == null) {
    		return 0;
    	}
    	visit(root);
    	return sum;
    }
    
    public void visit(TreeNode root) {
    	str += root.val;
    	if (root.left == null && root.right == null) {
    		int num = Integer.parseInt(str);
    		sum += num;
    	}
    	
    	if (root.left != null) {
    		visit(root.left);
    	}
    	if (root.right != null) {
    		visit(root.right);
    	}
    	
    	str = str.substring(0, str.length()-1);
    }
}

class Solution {
public:
    int ans = 0;
    void sum(TreeNode *p,int n=0){
        if(!p) return;
        n = n*10 + p->val;
        if(p->left==NULL&&p->right==NULL){
            ans += n;
            return;
        }
        sum(p->left,n);
        sum(p->right,n);
    }
    int sumNumbers(TreeNode *root) {
        sum(root);
        return ans;
    }
};

public class Solution {
    public int sumNumbers (TreeNode root) {
        if (root == null) return 0;
        ArrayList<String> res = new ArrayList<>();
        StringBuffer sb = new StringBuffer();
        dfs(root, sb, res);
        int sum = 0;
        for (int i = 0; i < res.size(); i++)
            sum = sum + Integer.parseInt(res.get(i));
        return sum;
    }
    void dfs(TreeNode root, StringBuffer sb, ArrayList<String> res){
        sb.append(root.val);
        if (root.left == null && root.right == null)
            res.add(sb.toString());
        if (root.left != null)
            dfs(root.left, sb, res);
        if (root.right != null)
            dfs(root.right, sb, res);
        sb.deleteCharAt(sb.length() - 1);        
    }   
}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int sumNumbers (TreeNode root) {
        //从根节点开始递归
        return fun(root, 0);
    }
    
    public static int fun(TreeNode root, int sum){
        //situation null
        if(root == null) return 0;
        //follow the instument
        sum = sum * 10 + root.val;
        //leaf situation
        if(root.left == null && root.right == null) return sum;
        //follow the instument
        return fun(root.left, sum) + fun(root.right,sum);
    }
}

public class Solution {
    /**
     *    问题是求二叉树所有根节点到子节点的路径
     *    我的思路是通过递归去遍历目标路径，通过传参传递截止到当前节点的数字
     *    如果是叶子节点，传入的数字已经是当前路径的数字，返回到父节点去求和
     *    每个上一级节点获取的是自己所在路径（1到多条）的数字和
     *    根节点获取的就是所有路径构成的数字和
     */
    public int sumNumbers(TreeNode root) {
        if(root == null) return 0;
        return dfs(root, 0);
    }
    public int dfs(TreeNode root, int sum){
        int n = 0;
        if(root.left!=null){
            n += dfs(root.left, sum*10+root.val);
        }
        if(root.right!=null){
            n += dfs(root.right, sum*10+root.val);
        }
        if(root.left==null&&root.right==null){
            n = sum*10+root.val;
        }
        return n;
    }
}

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
/*
利用后序遍历非递归的思想，先找到最左的一个叶子节点，在找的过程中，
将所有遍历节点入栈，入栈过程中利用tmp = tmp * 10 + T->val来储存先前遍历的节点的值累加，
直到找到叶子节点，然后将值加入ans中，继续寻找下一个叶子节点，直到叶子节点寻找完毕。
*/
class Solution {
public:
    int sumNumbers(TreeNode *root) {
        if(root == NULL)
            return 0;
        
        int ans = 0;
        int tmp = 0;
        
        TreeNode *T = root;
        TreeNode *v[50] = {NULL};
        stack<TreeNode *> s;
        int i = 0;
        while(T || !s.empty())
        {
            if(T)
            {
                s.push(T);
                tmp = tmp * 10 + T->val;
                T = T->left;
            }
            else
            {
                T = s.top();
                if(T->right&&!searV(v,T))
                {
                    T = T->right;
                }
                else
                {
                    if(!T->right&&!T->left)
                        ans = ans + tmp;
                    v[i] = T; i++;
                    s.pop(); tmp = (tmp - T->val) / 10;
                    T = NULL;
                }
            }
        }
        
        return ans;
    }
    
    bool searV(TreeNode *v[],TreeNode *T)
    {
        if (T) 
        {
            for (int i = 0; i < 50; i++)
            {
                if (v[i] == T->right) return 1;
            }
        }

        return 0;
    }
}; 

/*
坑：树为空时，返回0。
记当前节点的路径数字。遇到叶子节点时，将路径数字加到ans中。
返回ans。
*/
public class Solution {
    
    int ans = 0;
   
    public int sumNumbers(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

    public void dfs(TreeNode node, int sum) {
        sum = sum*10 + node.val;
        if (node.left == null && node.right == null) {
            ans += sum;
            return;
        }
        if (node.left != null) {
            dfs(node.left, sum);
        }
        if (node.right != null) {
            dfs(node.right, sum);
        }
    

class Solution {
public:
    int sumNumbers(TreeNode *root) {
        return sumNumbersCore(root, 0);
    }
private:
    int sumNumbersCore(TreeNode* root, int sum){  //sum表示到root节点的父节点的路径和
        if(root != nullptr){
            sum = 10*sum+root->val;
            int sumLeft = sumNumbersCore(root->left, sum);
            int sumRight = sumNumbersCore(root->right, sum);
            if(sumLeft != sum && sumRight != sum)
                sum = sumLeft+sumRight;
            else if(sumLeft != sum)
                sum = sumLeft;
            else if(sumRight != sum)
                sum = sumRight;
        }
         return sum;
    }
}; 

没人用后序，贴一个吧，虽然量大但适合解决所有路径问题，改对应处的访问代码即可

int sumOfVector(vector<int> sum){
    int res = 0;
    for(int i = 0; i < sum.size(); ++i){
        res *= 10;
        res +=  sum[i];
    }
    return res;
}
int sumNumbers(TreeNode *root){
    TreeNode* stk[1000] = {0};
    int top = -1;
    TreeNode *cur = root, *f_last = NULL;
    vector<int> res;
    long long totalSum = 0;
    while(cur || top != -1){
        if(cur){
            stk[++top] = cur;
            cur = cur->left;
        }
        else{
            cur = stk[top];
            if(cur->right && f_last != cur->right){
                cur = cur->right;
            }
            else{
                f_last = cur;
                if(cur->left == NULL && cur->right == NULL){
                    vector<int> sum;
                    for(int i = 0; i <= top; ++i)
                        sum.push_back(stk[i]->val);
                    res.push_back(sumOfVector(sum));
                }
                top--;
                cur = NULL;
            }
        }
    }
    for (int i = 0; i < res.size(); ++i)
        totalSum += res[i];
    return totalSum;
}

树的广度优先遍历
class Solution {
public:
    int sumNumbers(TreeNode *root) {
        int sum=0;
        if(root==NULL)
            return sum;
        queue<pair<TreeNode*,int>>qu;
        qu.push(make_pair(root,root->val));
        while(!qu.empty()){
            auto temp=qu.front();
            qu.pop();
            if(temp.first->left!=NULL){
                int cur=temp.second*10+temp.first->left->val;
                qu.push(make_pair(temp.first->left,cur));
            }
            if(temp.first->right!=NULL){
               int cur=temp.second*10+temp.first->right->val;
                qu.push(make_pair(temp.first->right,cur));
            }
            if(temp.first->left==NULL&&temp.first->right==NULL)
                sum+=temp.second;
        }
        return sum;
    }
};