English
101. Symmetric Tree
Problem Statement
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?
Solution:
go
package main
// Definition for a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func isSymmetric(root *TreeNode) bool {
return isMirror(root, root)
}
func isMirror(t1, t2 *TreeNode) bool {
if t1 == nil && t2 == nil {
return true
}
if t1 == nil || t2 == nil {
return false
}
return (t1.Val == t2.Val) && isMirror(t1.Left, t2.Right) && isMirror(t1.Right, t2.Left)
}
py
from out.definitions.treenode import TreeNode
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
return self._is_mirror(root, root)
def _is_mirror(self, t1: TreeNode, t2: TreeNode) -> bool:
if not t1 and not t2:
return True
if not t1 or not t2:
return False
return ((t1.val == t2.val) and
self._is_mirror(t1.right, t2.left) and
self._is_mirror(t1.left, t2.right))
...