Dare2Solve
A tree is symmetric if the left subtree is a mirror reflection of the right subtree. This means that for every node in the left subtree, there should be a corresponding node in the right subtree with the same value, and their children should also be mirror reflections of each other.
None
, the tree is symmetric by definition.None
, they are symmetric.None
, they are not symmetric.O(N), where N is the number of nodes in the binary tree. Each node is visited once.
O(H), where H is the height of the tree. This is due to the space required for the recursion stack. In the worst case (for a completely unbalanced tree), the height is N, and in the best case (for a completely balanced tree), the height is log(N).
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (!root) return true;
return helper(root->left, root->right);
}
private:
bool helper(TreeNode* root1, TreeNode* root2) {
if (root1 == nullptr && root2 == nullptr) return true;
if (root1 == nullptr || root2 == nullptr) return false;
if (root1->val != root2->val) return false;
return helper(root1->left, root2->right) && helper(root1->right, root2->left);
}
};
# 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: Optional[TreeNode]) -> bool:
if not root:
return True
return self.helper(root.left, root.right)
def helper(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
if root1 is None and root2 is None:
return True
if root1 is None or root2 is None:
return False
if root1.val != root2.val:
return False
return self.helper(root1.left, root2.right) and self.helper(root1.right, root2.left)
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return helper(root.left, root.right);
}
private boolean helper(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) return true;
if (root1 == null || root2 == null) return false;
if (root1.val != root2.val) return false;
return helper(root1.left, root2.right) && helper(root1.right, root2.left);
}
}
var isSymmetric = function (root)
{
if (!root) return true;
function helper(root1, root2)
{
if (root1 == null && root2 == null) return true;
if (root1 == null || root2 == null) return false;
if (root1.val !== root2.val) return false;
return helper(root1.left, root2.right) && helper(root1.right, root2.left);
}
return helper(root.left, root.right);
};