[leetcode]Sum Root to Leaf Numbers - java 回溯 深度遍历

主要是回溯算法结合树的深度遍历

 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int sumNumbers(TreeNode root) {
        if(root==null){
            return 0;
        }
        List<TreeNode> root2Leaf = new ArrayList<TreeNode>();
        root2Leaf.add(root);
        int[] sum = new int[1];
        backTrack(root, root2Leaf, sum);
        return sum[0];
    }

    private void backTrack(TreeNode node, List<TreeNode> root2Leaf, int[] sum){
        if(node.left==null && node.right==null){
            process(root2Leaf, sum);
        }
        TreeNode left = node.left;
        if(left != null){
            int size = root2Leaf.size();
            root2Leaf.add(left);
            backTrack(left, root2Leaf, sum);
            root2Leaf.remove(size);
        }
        TreeNode right = node.right;
        if(right != null){
            int size = root2Leaf.size();
            root2Leaf.add(right);
            backTrack(right, root2Leaf, sum);
            root2Leaf.remove(size);
        }
    }

    private void process(List<TreeNode> root2Leaf, int[] sum){
        int d = 0;
        for(int i=0; i<root2Leaf.size(); i++){
            d += (int)Math.pow(10, root2Leaf.size()-i-1) * root2Leaf.get(i).val;
        }
        sum[0] += d;
    }
}