ac solution code


  • 0
     /*
         Solutiol. time = O(n); space = O(n)  
         
         1. To verify the tree is symmetirc:
         1) l.val == r.val
         2) isSymmetirc(l.left, r.right)
         3) isSymmetirc(l.right, r.left)
    
         2. Termination case:
         l or r is nil: 1) return true if l and r are both nil, 2) otherwise false
    
              root
             /    \
            /      \
           l        r
          /  \      / \
         /    \    /   \
      left  right left right
         */
        func isSymmetric(_ root: TreeNode?) -> Bool {
            return isSymmetirc(root, root)
        }
        func isSymmetirc(_ l: TreeNode?, _ r: TreeNode?) -> Bool {
            if l == nil || r == nil{
                return (l == nil && r == nil)
            }
            return l!.val==r!.val && isSymmetirc(l!.left, r!.right) && isSymmetirc(l!.right, r!.left)
        }
    
    
    /*
         FOLLOW UP. What if node has left, mid, right children
         Solution: time = O(n); space = O(n)
    
         1. To verify the tree is symmetric:
         1) l.val == r.val
         2) isSymmetric(l.left, r.right)
         3) isSymmetric(l.right, r.left)
         4) isSymmetric(l.mid, r.mid) <<<<<< Verify l.mid is symmetric with r.mid. And it also verify isSymmetric(root.mid, root.mid) at first, to ensure root.mid itself is symmetric.
    
         2. Termination case:
         l or r is nil: 1) return true if l and r are both nil, 2) otherwise false
    
                root
             /    |   \
            /     |    \
           l      m     r
          / | \       / | \
         /  |  \     /  |  \
       left m right left m right
         */
        func isSymmetric(_ root: TreeNode?) -> Bool {
            return isSymmetric(root, root)
        }
        func isSymmetric(_ l: TreeNode?, _ r: TreeNode?) -> Bool {
            if l == nil || r == nil{
                return (l == nil && r == nil)
            }
            return l!.val==r!.val && isSymmetric(l!.left, r!.right) && isSymmetric(l!.right, r!.left) && isSymmetric(l!.mid, r!.mid)
        }
    

Log in to reply
 

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