Short recursive and Iterative with two stacks - java


  • 0
    D

    Recursive:

        public boolean isSymmetric(TreeNode root) {
            if(root==null) return true;
            return compare(root.left, root.right);
        }
        
        public boolean compare(TreeNode left, TreeNode right){
            if(left==null && right==null) return true;
            if(left==null || right==null) return false;
            
            return left.val==right.val && compare(left.left, right.right) && compare(left.right, right.left);
        }
    

    Iterative:

    public boolean isSymmetric(TreeNode root) {
            if(root==null) return true;
            TreeNode left=root.left;
            TreeNode right=root.right;
            Stack<TreeNode> stack1 = new Stack<TreeNode>();
            Stack<TreeNode> stack2 = new Stack<TreeNode>();
            
            if(left!=null) stack1.push(left);
            if(right!=null) stack2.push(right);
            
            while(!stack1.isEmpty() && !stack2.isEmpty()){
                if((left==null && right!=null) || (left!=null && right==null) || left.val!=right.val) return false;
                if(left.left!=null){
                    if(right.right==null) return false;
                    left=left.left;
                    right=right.right;
                }
                else{
                    if(right.right!=null) return false;
                    left=null;
                    right=null;
                    while(left==null && right==null && !stack1.isEmpty() && !stack2.isEmpty()){
                        left=stack1.pop().right;
                        right= stack2.pop().left;
                    }
                }
                if(left!=null) stack1.push(left);
                if(right!=null) stack2.push(right);
            }
            
            return stack1.isEmpty() && stack2.isEmpty();
        }

  • 0
    M

    Actually, for the iterative one, using one stack is enough. :)


Log in to reply
 

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