【2024考研】题解20 | #对称的二叉树#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param pRoot TreeNode类 
     * @return bool布尔型
     */
    bool recurison(TreeNode *pRoot1,TreeNode *pRoot2){
        //单个节点 对称
        if(pRoot1 == NULL && pRoot2 == NULL) return true;
        //单个空值 两点异值 不对称
        if(pRoot1 == NULL || pRoot2 == NULL || pRoot1->val != pRoot2->val) return false;
        //左右右左递归实现
        return recurison(pRoot1->left,pRoot2->right) && recurison(pRoot2->left,pRoot1->right);
    }
    bool isSymmetrical(TreeNode* pRoot) {
        // write code here
        // special case
        if(pRoot == NULL) return true;
        //左右右左递归实现
        return recurison(pRoot->left,pRoot->right);
    }
};

基本算法思想：

- 使用递归的方式判断二叉树是否是对称的。

- 对称的条件是：左子树的左子树和右子树的右子树相等，并且左子树的右子树和右子树的左子树相等。

- 在递归过程中，比较两个节点的值是否相等，并递归判断左子树和右子树是否对称。

时间复杂度：

O(n)，其中n是二叉树的节点个数。需要遍历每个节点一次。

空间复杂度：

O(n)，递归调用栈的深度最大为二叉树的高度，最坏情况下，二叉树是一个链表，高度为n，因此空间复杂度是O(n)。