[LeetCode] 129. Sum Root to Leaf Numbers

用户1148830

发布于 2018-01-03 17:46:47

5540

发布于 2018-01-03 17:46:47

文章被收录于专栏：来自地球男人的部落格

【原题】 Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

【解释】给一颗二叉树，要求返回其从根结点到叶子结点组成数字之和。从根结点到叶子结点从上到下对应从左到右。例如路径1->2，则代表数字为12. 【思路】基本上和Path Sum II同样的思路，上篇博文也有。思路基本相同，只不过在找到满足条件的子集之后，本题要做的是加和。

public class Solution {
    private int sum=0;
    public int getNum(List<Integer> list){//得到所在list所有值的正数表示
        int res=0;
        for(int i=0;i<list.size();i++){
            res=res*10+list.get(i);
        }
        return res;
    }
    public void sumNumbersCore(List<Integer> list, TreeNode root){
        list.add(root.val);
        if(root.left==null&&root.right==null)
            sum+=getNum(list);//将所有路径代表的数字累加
        else{
            if(root.left!=null)
                sumNumbersCore(list,root.left);
            if(root.right!=null)
                sumNumbersCore(list,root.right);
        }
        list.remove(list.size()-1);
    }
    public int sumNumbers(TreeNode root) {
        if(root==null) return 0;//空树
        List<Integer> list=new ArrayList<Integer>();
        sumNumbersCore(list,root);
        return sum;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2017年06月29日，如有侵权请联系 cloudcommunity@tencent.com 删除

digits