Share my iterative Java solution


  • 0
    T
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null)
            return result;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        Stack<LinkedList<Integer>> paths = new Stack<LinkedList<Integer>>();
        stack.push(root);
        paths.push(new LinkedList<Integer>(Arrays.asList(root.val, root.val)));
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            LinkedList<Integer> path = paths.pop();
            if (node.left == null && node.right == null && path.pollFirst() == sum)
                result.add(path);
            if (node.left != null) {
                stack.push(node.left);
                LinkedList<Integer> p = new LinkedList<Integer>(path);
                p.add(node.left.val);
                p.set(0, p.peekFirst() + p.peekLast());
                paths.push(p);
            }
            if (node.right != null) {
                stack.push(node.right);
                LinkedList<Integer> p = new LinkedList<Integer>(path);
                p.add(node.right.val);
                p.set(0, p.peekFirst() + p.peekLast());
                paths.push(p);
            }
        }
        return result;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.