二叉树路径求和

84 阅读 0 评论 56 点赞

我是靠谱客的博主虚幻西牛，最近开发中收集的这篇文章主要介绍二叉树路径求和，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

二叉树路径和

给定一棵二叉树，二叉树权值为0-9，得出所有根节点到叶节点的路径和。如下图的二叉树，路径和n=137+15=152

3 5

知道用递归遍历i每条路径：但是具体做法还是请教了我对象，下面是我的代码，还有个句话要说就是这道题和《剑指offer》中的找到路径和为22的路径相似，都是要找出所有路径，这道题见http://blog.csdn.net/luxiaoxun/article/details/7537605

下面是求每条路径的路径和：

package binayTree;

/**
 * Created by Administrator on 2015/10/30 0030.
 */



import java.util.ArrayList;
import java.util.Stack;

/**
 * Created by chen on 2015/10/30.
 */
class Solution1 {
    ArrayList<String> list1 = new ArrayList<String>();
    Integer sum = 0;
    Stack<Integer> stack=new Stack<Integer>();

    public static void main(String[] args) {
        Solution1 s = new Solution1();
        Stack<Integer> stack=new Stack<Integer>();
        Node root = new Node(1);
        Node node1 = new Node(3);
        Node node2 = new Node(5);
        Node node3 = new Node(7);
        root.left = node1;
        root.right = node2;
        node1.right = node3;

        System.out.println(s.sumNumbers(root));

    }

    public int sumNumbers(Node root) {

        if (root == null)
            return 0;
        stack.push(root.value);


        // root to this leaf load sum
        if (root.left == null && root.right == null) {
            int now = 0;
            for (Integer i : stack) {
                now = now * 10 + i;
            }
            sum += now;


        } else {
            if (root.left != null) {
                sumNumbers(root.left);
                stack.pop();
            }
            if (root.right != null) {
                sumNumbers(root.right);
                stack.pop();
            }

        }
        return sum;
    }

}