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

Note:
Bonus points if you could 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, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root is None:
            return True
        
        return self.isMirror(root.left, root.right)
        
    def isMirror(self, root1, root2):
        
        if root1 == None and root2 == None:
            return True
        
        if root1 == None or root2 == None:
            return False       

        if root1.val != root2.val:
            return False
        
        return root1.val == root2.val and self.isMirror(root1.left, root2.right) and self.isMirror(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.

One Thought to “LeetCode 101. Symmetric Tree”

Leave a Reply

Your email address will not be published. Required fields are marked *