刷代码随想录有感（44）：对称二叉树

题干：

代码：

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right){//传入左右子树
        if(left == NULL && right != NULL) return false;//子
        else if(left != NULL && right == NULL) return false;//子
        else if(left == NULL && right == NULL) return true;//子
        else if(left -> val != right -> val) return false;//子
        
        bool inside = compare(left -> right, right -> left);//父
        bool outside = compare(left -> left, right -> right);//父
        bool res = inside && outside;//父
        return res;
    }
    bool isSymmetric(TreeNode* root) {
        bool res = compare(root -> left, root -> right);
        return res;
    }
};

某种意义上是后序遍历。

补充：迭代实现：
 

//实现二叉树是否对称的迭代方法，我们可以使用队列。基本思路是利用队列存储需要比较的节点，每次取出两个节点比较它们的值，然后按照镜像的方式将它们的子节点成对加入队列。以下是一个具体实现的示例：
bool isSymmetric(TreeNode* root) {
    if (root == NULL) return true;//用于降低时间复杂度
    
    // 使用队列来迭代处理
    queue<TreeNode*> q;
    // 初始时将根节点的左右子节点加入队列
    q.push(root->left);
    q.push(root->right);
    
    while (!q.empty()) {
        TreeNode* leftnode = q.front(); 
        q.pop();
        TreeNode* rightnode = q.front(); 
        q.pop();
        // 如果两个节点都为空，则继续下一轮比较,说明此时已经顺利遍历到叶子了
        if (leftnode == NULL && rightnode == NULL) continue;
        // 只要遍历过程中出现其中一个节点为空，或者两个节点的值不相等，则不对称，立刻返回false
        if (!leftnode || !rightnode || leftnode->val != rightnode->val) return false;
        // 将要比较的子节点成对加入队列
        q.push(leftnode->left);//外
        q.push(rightnode->right);//外
        q.push(leftnode->right);//内
        q.push(rightnode->left);//内
    }
    
    return true; // 能顺利完成while说明每一次都能顺利达到left == NULL && right == NULL，返回 true
}

原理其实也就是镜像比较两个节点值是否相同。