题解 | #二叉树根节点到叶子节点的所有路径和#

打印所有路径 当递归到叶子节点时 把路径加入结果集合 什么是叶子节点就是左子树 和右子树为null

回溯思想 加入后面也要删除

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) {
        // write code here
        if (root == null){
            return  0;
        }
        Deque<Integer>  deque = new LinkedList<>();
        List<Integer>  res =  new ArrayList<>();
        dfs(root,deque,res);
        int m = res.size();
        int sum = 0;
        for (int i = 0; i < m; i++) {
            sum += res.get(i);
        }

        return  sum;
    }


    public  void  dfs(TreeNode root, Deque<Integer> deque, List<Integer> res){
        if (root == null){
            return;
        }
        deque.addLast(root.val);
        if (root.left==null && root.right == null){
            List<Integer> ans = new ArrayList<>(deque);
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < ans.size(); i++) {
                builder.append(ans.get(i));
            }
            String temp = builder.toString();
            Integer num = Integer.parseInt(temp);
            res.add(num);
        }
        dfs(root.left, deque, res);
        dfs(root.right,deque,res);
        if (!deque.isEmpty()){
            deque.removeLast();
        }
    }
}