题解 | #牛群的轴对称结构# 二叉树应用题

知识点

二叉树

思路分析

要判断一棵二叉树是不是对称的。

首先空树一定是满足条件的。假如这个树非空，我们从根节点自顶向下，除了根节点以外应该可以找到对称的匹配节点（只有根节点找不到对称节点）。那么我们定义一个函数check，来判断以r1和r2两个节点为根节点的子树是否是对称的。对于两个节点来说要求他们是满足check要求的，一定值要相等，或者都为空节点，如果不为空那么左右子树对应也要满足check。这样自顶向下递归下去即可判断。

时间复杂度

每个节点只访问了常数次，时间复杂度为

AC code（C++）

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return check(root->left, root->right);
    }
    bool check(TreeNode* r1, TreeNode* r2) {
        if (!r1 and !r2) return true; // 都为空
        if (!r1 or !r2) return false; // 有一个为空 一个不为空
        if (r1->val != r2->val) return false;
        return check(r1->left, r2->right) and check(r1->right, r2->left);
    }
};