Java, DFS, Iterative, two stack


  • 1
    S
    public boolean hasPathSum(TreeNode root, int result){
        if(root == null)
            return false;
        ArrayList<Integer> list = new ArrayList<Integer>();
        ArrayDeque<TreeNode> stack = new ArrayDeque<TreeNode>();
        ArrayDeque<Integer> sums = new ArrayDeque<Integer>();
        stack.push(root);
        sums.push(0);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            int sum = sums.pop() + cur.val;
            if(cur.left == null && cur.right == null){
                if(sum == result)
                    return true;
            }
            if(cur.left != null){
                stack.push(cur.left);
                sums.push(sum);
            }
            if(cur.right != null){
                stack.push(cur.right);
                sums.push(sum);
            }
        }
        return false;
    }

Log in to reply
 

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