101. 对称二叉树

力扣题目链接 (opens new window)

题目描述

给你一个二叉树的根节点 root，检查它是否轴对称。

示例 1：

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

示例 2：

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

思路

判断对称，要比较的是根节点的左右孩子吗？只比较这两个值显然不够。要比较左子树和右子树是不是互为镜像，所以递归函数一次接收两个节点。这也是代码随想录原题首先强调的点。

先处理空节点：都为空则对称，只有一个为空则不对称。都非空时，数值不同也不对称。剩下的情况要同时比较外侧 left->left 与 right->right，以及内侧 left->right 与 right->left。

模拟过程

主站的这张图展示了外侧与内侧的对应关系：

以 [1,2,2,3,4,4,3] 为例，两个 2 数值相同；外侧的两个 3 相同，内侧的两个 4 相同；继续比较对应的空孩子，也都成对为空，所以结果为 true。

解题代码

class Solution {
    bool compare(TreeNode* left, TreeNode* right) {
        if (left == nullptr && right == nullptr) return true;
        if (left == nullptr || right == nullptr) return false;
        if (left->val != right->val) return false;
        // 外侧和内侧都要相等，才能构成镜像
        return compare(left->left, right->right) &&
               compare(left->right, right->left);
    }
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;
        return compare(root->left, root->right);
    }
};

复杂度分析

• 时间复杂度：O(n)，最多比较所有节点。
• 空间复杂度：O(h)，递归栈占用树高 h。

其他语言

Python3

class Solution:
    def isSymmetric(self, root):
        def compare(left, right):
            if left is None or right is None:
                return left is right
            return (left.val == right.val and
                    compare(left.left, right.right) and
                    compare(left.right, right.left))
        return True if root is None else compare(root.left, root.right)

Java

class Solution {
    boolean compare(TreeNode left, TreeNode right) {
        if (left == null || right == null) return left == right;
        if (left.val != right.val) return false;
        return compare(left.left, right.right) && compare(left.right, right.left);
    }
    public boolean isSymmetric(TreeNode root) {
        return root == null || compare(root.left, root.right);
    }
}

Go

func isSymmetric(root *TreeNode) bool {
    var compare func(*TreeNode, *TreeNode) bool
    compare = func(left, right *TreeNode) bool {
        if left == nil || right == nil { return left == right }
        return left.Val == right.Val &&
            compare(left.Left, right.Right) && compare(left.Right, right.Left)
    }
    return root == nil || compare(root.Left, root.Right)
}

JS

var isSymmetric = function(root) {
    function compare(left, right) {
        if (left === null || right === null) return left === right;
        return left.val === right.val &&
            compare(left.left, right.right) && compare(left.right, right.left);
    }
    return root === null || compare(root.left, root.right);
};

与代码随想录联系

101.对称二叉树把空节点判断和内外侧比较讲得更细，也给了队列、栈的写法。录友如果觉得“同时递归两棵树”别扭，先看原题的配图再写代码。