C# - iterative using 2 stacks, with clear explaination


  • 0

    You can alternately use 1 stack as posted on several solutions, but I like the 2 stacks to me it's easier to read.

        public bool IsSymmetric(TreeNode root) 
        {
            Stack<TreeNode> left = new Stack<TreeNode>();
            Stack<TreeNode> right = new Stack<TreeNode>();
            
            if (root == null) return true;
            
            left.Push(root.left);
            right.Push(root.right);
            
            // traverse along left and right sides step for step checking
            // symmetry at each iteration
            while (left.Count > 0 && right.Count > 0)
            {
                TreeNode nodeLeft = left.Pop();
                TreeNode nodeRight = right.Pop();
                
                // both sides Null is symmetric
                if (nodeLeft == null && nodeRight == null)   continue;
                
                // not symmetric - terminate early
                if ((nodeLeft == null || nodeRight == null) || (nodeLeft.val != nodeRight.val)) return false;
                
                // Left Tree - left on top of stack
                left.Push(nodeLeft.right);
                left.Push(nodeLeft.left);
                
                // Right Tree - right on top of stack
                right.Push(nodeRight.left);
                right.Push(nodeRight.right);
            }
            
            // to this point all left and right nodes have been symmetric
            // check both stacks are empty then the tree is symmetric
            return left.Count == 0 && right.Count == 0;
        }
    

Log in to reply
 

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