LeetCode 101. Symmetric Tree

Description

https://leetcode.com/problems/symmetric-tree/description/

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

Follow up: Solve it both recursively and iteratively.

Explanation

The key point is to implement isMirror(TreeNode node1, TreeNode node2) function.

There are two scenarios for isMirror(TreeNode node1, TreeNode node2) to return true:

1. when node1 and node2 are both null
2. when node1 and node2 aren’t null, node1 and node2 should have same value and node1’s left should be the mirror for node2’s right and node1’s right should be the mirror node2.left subtrees.

Java Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        return isMirror(root.left, root.right);
    }
    
    private boolean isMirror(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) {
            return true;
        }
        
        if (node1 == null || node2 == null) {
            return false;
        }
        
        if (node1.val != node2.val) {
            return false;
        }        
        
        return node1.val == node2.val && isMirror(node1.left, node2.right) && isMirror(node1.right, node2.left);
    }
}

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        
        if not root.left and not root.right:
            return True        
        
        return self.is_mirror(root.left, root.right)
        
    def is_mirror(self, root1, root2):
        if not root1 and not root2:
            return True            

        if not root1 or not root2 or root1.val != root2.val:
            return False
        
        return self.is_mirror(root1.left, root2.right) and self.is_mirror(root1.right, root2.left)

• Time complexity: O(N). Because we traverse the entire input tree once, the total run time is O(N), where N is the total number of nodes in the tree.
• Space complexity: The number of recursive calls is bound by the height of the tree. In the worst case, the tree is linear and the height is in O(N). Therefore, space complexity due to recursive calls on the stack is O(N) in the worst case.