JAVA DFS by one stack 1ms


  • 0
    E

    We can solve the problem in DFS by one stack instead of two. But it needs to run stack.size()%2 != 0 for several times. Any better idea about it?

    public boolean isSameTree(TreeNode p, TreeNode q) {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            if (p != null) { stack.push(p); }
            if (q != null) { stack.push(q); }
    
            while (!stack.isEmpty() && stack.size()%2 == 0) {
                TreeNode pn = stack.pop();
                TreeNode qn = stack.pop();
                if (pn.val != qn.val) return false;
                if (pn.right != null) stack.push(pn.right);
                if (qn.right != null) stack.push(qn.right);
                if (stack.size()%2 != 0) return false;
                if (pn.left != null) stack.push(pn.left);
                if (qn.left != null) stack.push(qn.left);
                if (stack.size()%2 != 0) return false;
            }
            if (stack.size()%2 != 0) { return false; }
            else { return true; }
        }
    

  • 2
    P

    @eatbanli You can allow null values in the stack, or use a TreePair holder class to hold two nodes.

    public boolean isSameTree(TreeNode p, TreeNode q) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(q);
        stack.push(p);
    
        while (!stack.isEmpty()) {
            TreeNode pn = stack.pop();
            TreeNode qn = stack.pop();
            if (pn == null && qn == null) {
                continue;
            } else if (pn == null || qn == null) {
                return false;
            } else if (pn.val != qn.val) {
                return false;
            }
            stack.push(pn.right);
            stack.push(qn.right);
            stack.push(pn.left);
            stack.push(qn.left);
        }
        return true;
    }

Log in to reply
 

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