C# accepted, IsSymmetricTree, Recursive and Non-Recursive


  • 1
    R

    IsSymmetricTree, Recursive and Non-Recursive

    // Recursive   
        public bool IsSymmetric(TreeNode root)
        {  
            if (root == null)
            {
                return true;
            }
            return IsSym(root.left, root.right);
        }
        
        public bool IsSym(TreeNode t1, TreeNode t2)
        {
            if (t1 == null && t2 == null)
            {
                return true;
            }
            
            if (t1 == null || t2 == null)
            {
                return false;
            }
            
            if (t1.val != t2.val)
            {
                return false;
            }
            
            return IsSym(t1.left, t2.right) && IsSym(t1.right, t2.left);
        }
        
    
    // NonRecursive
    
        public bool IsSymmetric(TreeNode root) 
        {
            Stack<TreeNode> s1 = new Stack<TreeNode>();
            Stack<TreeNode> s2 = new Stack<TreeNode>();
            TreeNode t1 = root;
            TreeNode t2 = root;
            while (s1.Count > 0 || t1 != null)
            {
                while (t1 != null)
                {
                    s1.Push(t1);
                    t1 = t1.left;
                }
                
                while (t2 != null)
                {
                    s1.Push(t2);
                    t2 = t2.right;
                }
                
                if (s1.Count != s2.Count)
                {
                    return false;
                }
                
                if (s1.Count > 0 && s2.Count > 0)
                {
                    t1 = s1.Pop();
                    t2 = s2.Pop();
                    if (t1.val != t2.val)
                    {
                        return false;
                    }
                    t1 = t1.right;
                    t2 = t2.left;
                }
                else
                {
                    t1 = null;
                    t2 = null;
                }
            }
            return true;
        }

Log in to reply
 

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