剑指 Offer 28. 对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
示例 1：
输入：root = [1,2,2,3,4,4,3] 输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3] 输出：false
限制：
0 <= 节点个数 <= 1000
注意：本题与主站 101 题相同：https://leetcode.cn/problems/symmetric-tree/
原站题解
php 解法, 执行用时: 12 ms, 内存消耗: 15.1 MB, 提交时间: 2021-05-10 17:06:14
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($value) { $this->val = $value; }
* }
*/
class Solution {
/**
* @param TreeNode $root
* @return Boolean
*/
function isSymmetric($root) {
if ( $root == null ) return true;
return $this->isSame($root->left, $root->right);
}
function isSame($left, $right) {
if ( $left == null && $right == null ) return true;
if ( $left == null || $right == null || $left->val != $right->val ) return false;
return $this->isSame($left->left, $right->right) && $this->isSame($left->right, $right->left);
}
}
golang 解法, 执行用时: 4 ms, 内存消耗: 2.9 MB, 提交时间: 2020-11-17 22:42:13
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSymmetric(root *TreeNode) bool {
if root == nil {
return true
}
return helper(root.Left, root.Right)
}
func helper(node1 *TreeNode, node2 *TreeNode) bool {
if node1 == nil && node2 == nil {
return true
}
if node1 == nil || node2 == nil || node1.Val != node2.Val {
return false
}
return helper(node1.Left, node2.Right) && helper(node2.Left, node1.Right)
}
python3 解法, 执行用时: 48 ms, 内存消耗: 13.6 MB, 提交时间: 2020-11-17 22:36:29
# 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:
def recur(L, R):
if not L and not R: return True
if not L or not R or L.val != R.val: return False
return recur(L.left, R.right) and recur(L.right, R.left)
return recur(root.left, root.right) if root else True