本问题对应的 leetcode 原文链接：剑指 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

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

限制：

• 0 <= 节点个数 <= 1000

解题思路

视频讲解直达： 本题视频讲解

代码实现

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)){
            return true;
        }

        return f(root.left, root.right);
    }
    // 判断B是不是以A阶段为根节点的子树
    public boolean f(TreeNode A, TreeNode B){
        if(A == null && B == null){
            return true;
        }

        if(A == null || B == null){
            return false;
        }

        if(A.val != B.val){
            return false;
        }

        return f(A.left, B.right) && f(A.right, B.left);
    }
}

时间复杂度：O(n)
空间复杂度：树的高度

Python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root or (not root.left and not root.right):
            return True

        return self.f(root.left, root.right)

    # 判断B是不是以A阶段为根节点的子树
    def f(self, A, B):
        if not A and not B:
            return True

        if not A or not B:
            return False

        if A.val != B.val:
            return False

        return self.f(A.left, B.right) and self.f(A.right, B.left)

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root || (!root->left && !root->right)) {
            return true;
        }

        return f(root->left, root->right);
    }

    // 判断B是不是以A阶段为根节点的子树
    bool f(TreeNode* A, TreeNode* B) {
        if (!A && !B) {
            return true;
        }

        if (!A || !B) {
            return false;
        }

        if (A->val != B->val) {
            return false;
        }

        return f(A->left, B->right) && f(A->right, B->left);
    }
};

Go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    if root == nil || (root.Left == nil && root.Right == nil) {
        return true
    }

    return f(root.Left, root.Right)
}

// 判断B是不是以A阶段为根节点的子树
func f(A *TreeNode, B *TreeNode) bool {
    if A == nil && B == nil {
        return true
    }

    if A == nil || B == nil {
        return false
    }

    if A.Val != B.Val {
        return false
    }

    return f(A.Left, B.Right) && f(A.Right, B.Left)
}

JS

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if (root == null || (root.left == null && root.right == null)) {
        return true;
    }

    return f(root.left, root.right);
};
// 判断 B 是不是以 A 阶段为根节点的子树
var f = function(A, B) {
    if (A == null && B == null) {
        return true;
    }

    if (A == null || B == null) {
        return false;
    }

    if (A.val !== B.val) {
        return false;
    }

    return f(A.left, B.right) && f(A.right, B.left);
};

shuaidi永久会员

收藏 海报挣佣金 推广链接