LeetCode101 对称二叉树

发表于 | 分类于 |
字数统计: 318 | 阅读时长 ≈ 1

链接: https://leetcode-cn.com/problems/symmetric-tree

题意

给定一个二叉树，检查它是否是镜像对称的。

解法

判断一个树是否对称等价于判断左右子树是否对称。一般习惯将判断两个子树是否相等或对称类型的题的解法叫做“四步法”：

  1. 如果两个子树都为空指针，则它们相等或对称
  2. 如果两个子树只有一个为空指针，则它们不相等或不对称
  3. 如果两个子树根节点的值不相等，则它们不相等或不对称
  4. 根据相等或对称要求，进行递归处理。

利用递归的思路进行解题，每次判断左节点的左节点是否和右节点的右节点对称 以及 左节点的右节点是否和右节点的左节点对称

递归神奇的地方就在于，你好像什么都没做，其实已经做完了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return root ? solve(root -> left, root -> right) : true;
    }

    bool solve(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 solve(left -> left, right -> right) && solve(left -> right, right -> left);
    }
};