34.二叉树中和为某一值的路径

raylan.chen大约 2 分钟

尝试着使用迭代遍历的先序遍历去遍历二叉树，但是 “非叶子节点”不知道怎么出队（存储路径的队列）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> pathTarget(TreeNode root, int target) {
        if (root == null) return new ArrayList<List<Integer>>();
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> tmpRes = new ArrayList<>();
        //先序遍历
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.offerLast(root);
        while (!stack.isEmpty()) {
            TreeNode tmp = stack.peekLast();
            tmpRes.add(tmp.val);

            if (tmp.right != null) stack.offerLast(tmp.right);
            if (tmp.left != null) stack.offerLast(tmp.right);
            
            if (tmp.left == null && tmp.right == null){
                int sum = 0;
                for (int i : tmpRes) {
                    sum += i;
                }
                //这里有错，res.add(new ArrayList(tmpRes));
                if (sum == target) res.add(new ArrayList<List<Integer>>(tmpRes));
                //这里有错，res.removeLast();
                tmpRes.remove();
            }
            //那非“叶子节点”该如何出队列？
        }
        return res;
    }
}

貌似先序遍历（递归）“自带回头”貌似会更方便些？

用栈来存储遍历顺序，该怎么走回头路呢？

优秀题解

class Solution {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathTarget(TreeNode root, int target) {
        recur(root, target);
        return res;
    }
    void recur(TreeNode root, int tar) {
        if(root == null) return;
        path.add(root.val);
        tar -= root.val;
        if(tar == 0 && root.left == null && root.right == null)
            res.add(new LinkedList(path));
        recur(root.left, tar);
        recur(root.right, tar);
        path.removeLast();
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/solutions/154060/mian-shi-ti-34-er-cha-shu-zhong-he-wei-mou-yi-zh-5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

tar -= root.val 可真秒呀！

34.二叉树中和为某一值的路径

34.二叉树中和为某一值的路径

参考链接

个人尝试

优秀题解