题目描述

给定一个仅包含数字0-9的二叉树，每一条从根节点到叶子节点的路径都可以用一个数字表示。
例如根节点到叶子节点的一条路径是1->2->3,那么这条路径就用123来代替。
找出根节点到叶子节点的所有路径表示的数字之和
例如：
1↵ / ↵ 2 3
根节点到叶子节点的路径1->2用数字12代替
根节点到叶子节点的路径1->3用数字13代替
所以答案为12+13=25

代码一

思路：不太懂21行为什么要new一个空间来存放arr

  1. static ArrayList<List<Integer>> list = new ArrayList<List<Integer>>();
  2.     static List<Integer> arr = new ArrayList<Integer>();
  3.     public static int sumNumbers (TreeNode root) {
  4.         if(root==null)return 0;
  5.         iter(root);        
  6.         int sum = 0;
  7.         for(int i=0;i<list.size();i++) {
  8.             int m = 1;
  9.             for(int j=list.get(i).size()-1;j>=0;j--) {
  10.                 sum += list.get(i).get(j)*m;
  11.                 m = m*10;
  12.             }            
  13.         }
  14.         return sum;
  15.     }
  16.     public static void iter(TreeNode root) {        
  17.         if(root!=null){    
  18.             arr.add(root.val);
  19.             System.out.println(System.identityHashCode(arr));
  20.             if(root.left==null&&root.right==null) {            
  21.                 list.add(new ArrayList<Integer>(arr));    
  22.                 System.out.println(System.identityHashCode(new ArrayList<Integer>(arr)));
  23.             }    
  24.             if(root.left!=null)
  25.                 iter(root.left);
  26.             if(root.right!=null)
  27.                 iter(root.right);
  28.         }
  29.         arr.remove(arr.size()-1);
  31.     }

代码二

public int sumNumbers(TreeNode root) {
    int sum = 0;
    if (root == null) {
        return sum;
    }
    return preorderSumNumbers(root, sum);
}
public int preorderSumNumbers(TreeNode root, int sum) {
    if (root == null)
        return 0;
    sum = sum * 10 + root.val;
    if (root.left == null && root.right == null) {
        return sum;
    }
    return preorderSumNumbers(root.left, sum) + preorderSumNumbers(root.right, sum);
}