0101. Symmetric Tree

Easy | Tree | 24 ms (99.01%), 14.2 MB (93.95%)

❓ Problem Statement

Source: LeetCode - Symmetric Tree GitHub: Solution / Performance

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

✍🏻 Constraints & Example

Constraints:

• The number of nodes in the tree is in the range [1, 1000].

• -100 <= Node.val <= 100

Input: root = [1,2,2,3,4,4,3]
Output: true

Input: root = [1,2,2,null,3,null,3]
Output: false

💡 Ideas

While this problem is easy and straightforward, we should be careful with the boundary conditions for both recursive and iterative methods.

Iterative

If both nodes are null, move to the next loop without pushing any nodes onto the stack. If one of the nodes is null, return False. If two nodes' values are different, return False.

Recursive

If both nodes are null, return True. If one of the nodes is null, return False.

🤖 Python3

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        # (base case)
        if not root.left and not root.right: return True
        
        # ==================================================
        #  Tree                               (Iterative)  =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        stack = [(root.left, root.right)]
        while stack:
            node1, node2 = stack.pop()
            
            # no child nodes, continue instead of pushing null nodes
            if not (node1  or node2): continue
                
            if not (node1 and node2): return False
            if node1.val != node2.val: return False
            
            stack.append((node1.left,  node2.right))
            stack.append((node1.right, node2.left))
            
        return True

        '''
        # ==================================================
        #  Tree                               (Recursive)  =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        def isMirror(leftNode, rightNode):
            if not leftNode and not rightNode: return True
            if not leftNode or  not rightNode: return False
            
            return (leftNode.val == rightNode.val)              \
                and isMirror(leftNode.left,  rightNode.right)   \
                and isMirror(leftNode.right, rightNode.left)
        
        return isMirror(root.left, root.right)
        '''

🤖 Java

class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */

    public boolean isMirror(TreeNode node1, TreeNode node2) {
        if(node1 == null && node2 == null) return true;
        if(node1 == null || node2 == null) return false;
        
        return (node1.val == node2.val) && 
               isMirror(node1.left,  node2.right) &&
               isMirror(node1.right, node2.left);
    }
    
    public boolean isSymmetric(TreeNode root) {
        /* base case */
        if(root.left == null && root.right == null) return true;
        
        return isMirror(root.left, root.right);
    }
}