Non-recusive solution for Path Sum II problem


  • 1
    Y

    Recursive solution is pretty straightforward, so I take some time to do the practice of non-recursive solution, it's a little troublesome and is easy to make mistake here.

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList();
        if(root == null) return res;
        
        Stack<TreeNode> stack = new Stack();
        Set<TreeNode> set = new HashSet();
        stack.push(root);
        set.add(root);
        int tmp = root.val;
        while(!stack.isEmpty()){
            TreeNode top = stack.peek();
            if(top.left != null && !set.contains(top.left)){
                stack.push(top.left);
                set.add(top.left);
                tmp += top.left.val;
            }else if(top.right != null && !set.contains(top.right)){
                stack.push(top.right);
                set.add(top.right);
                tmp += top.right.val;
            }else {
                if(top.left == null && top.right == null && tmp == sum){
                    ArrayList list = new ArrayList();
                    for(TreeNode node : stack){
                        list.add(node.val);
                    }
                    res.add(list);
                }
                tmp = tmp - stack.pop().val;
            }
        }
        
        return res;
    }

Log in to reply
 

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