Description:
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Examples:
Example 1:
Input: root = [1,2,2,3,4,4,3]
Output: true
Example 2:
Input: root = [1,2,2,null,3,null,3]
Output: falseSolution in Python:
The recursive approach involves checking whether the left subtree is a mirror reflection of the right subtree. We create a helper function to compare two nodes.
Python
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
def isMirror(left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
# If both nodes are None, they are symmetric
if not left and not right:
return True
# If only one of the nodes is None, they are not symmetric
if not left or not right:
return False
# The nodes must have the same value and their respective subtrees must be mirrors
return (left.val == right.val and
isMirror(left.left, right.right) and
isMirror(left.right, right.left))
return isMirror(root.left, root.right)Explanation
- We define a helper function
isMirrorthat checks if two trees are mirror images. - The base cases handle when both nodes are
None(symmetric) or one isNone(not symmetric). - We compare the current nodes and recursively check their children in the mirrored order (
left.leftwithright.rightandleft.rightwithright.left).
Solution in Javascript:
JavaScript
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
// If the tree is empty, it is symmetric
if (!root) {
return true;
}
// Helper function to check if two trees are mirror images
const isMirror = function(left, right) {
// If both nodes are null, they are symmetric
if (!left && !right) {
return true;
}
// If only one of the nodes is null, they are not symmetric
if (!left || !right) {
return false;
}
// Check if the current nodes have the same value and
// recursively check their subtrees in mirrored order
return (left.val === right.val &&
isMirror(left.left, right.right) &&
isMirror(left.right, right.left));
};
// Check if the left and right subtrees of the root are mirrors
return isMirror(root.left, root.right);
};Solution in Java:
Java
class Solution {
public boolean isSymmetric(TreeNode root) {
// If the tree is empty, it is symmetric
if (root == null) {
return true;
}
// Use the helper function to check if the left and right subtrees are mirrors
return isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode left, TreeNode right) {
// If both nodes are null, they are symmetric
if (left == null && right == null) {
return true;
}
// If only one of the nodes is null, they are not symmetric
if (left == null || right == null) {
return false;
}
// Check if the current nodes have the same value and
// recursively check their subtrees in mirrored order
return (left.val == right.val &&
isMirror(left.left, right.right) &&
isMirror(left.right, right.left));
}
}Solution in C#:
C#
public class Solution {
public bool IsSymmetric(TreeNode root) {
// If the tree is empty, it is symmetric
if (root == null) {
return true;
}
// Use the helper function to check if the left and right subtrees are mirrors
return IsMirror(root.left, root.right);
}
private bool IsMirror(TreeNode left, TreeNode right) {
// If both nodes are null, they are symmetric
if (left == null && right == null) {
return true;
}
// If only one of the nodes is null, they are not symmetric
if (left == null || right == null) {
return false;
}
// Check if the current nodes have the same value and
// recursively check their subtrees in mirrored order
return (left.val == right.val &&
IsMirror(left.left, right.right) &&
IsMirror(left.right, right.left));
}
}