Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
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: false
Constraints:
The number of nodes in the tree is in the range [1, 1000].
-100 <= Node.val <= 100
Follow up: Could you solve it both recursively and iteratively?
Solutions
Solution 1: Recursion
We design a function $dfs(root1, root2)$ to determine whether two binary trees are symmetric. The answer is $dfs(root, root)$.
The logic of the function $dfs(root1, root2)$ is as follows:
If both $root1$ and $root2$ are null, then the two binary trees are symmetric, return true.
If only one of $root1$ and $root2$ is null, or if $root1.val \neq root2.val$, then the two binary trees are not symmetric, return false.
Otherwise, determine whether the left subtree of $root1$ is symmetric to the right subtree of $root2$, and whether the right subtree of $root1$ is symmetric to the left subtree of $root2$. Here we use recursion.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 910111213141516
# 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 = rightclassSolution:defisSymmetric(self,root:Optional[TreeNode])->bool:defdfs(root1,root2):ifroot1isNoneandroot2isNone:returnTrueifroot1isNoneorroot2isNoneorroot1.val!=root2.val:returnFalsereturndfs(root1.left,root2.right)anddfs(root1.right,root2.left)returndfs(root,root)
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcisSymmetric(root*TreeNode)bool{vardfsfunc(*TreeNode,*TreeNode)booldfs=func(root1,root2*TreeNode)bool{ifroot1==nil&&root2==nil{returntrue}ifroot1==nil||root2==nil||root1.Val!=root2.Val{returnfalse}returndfs(root1.Left,root2.Right)&&dfs(root1.Right,root2.Left)}returndfs(root,root)}