题解 | #对称的二叉树#

方法一：递归

一个对称的二叉树，两个不同方向的前序遍历一定是相同的。通过递归进行两个方向的遍历，终止条件为：当两个节点只有一个为空，或者两个节点的值不相同，则二叉树不对称。

时间复杂度：o(n)

空间复杂度：o(n)。递归栈的深度

class Solution {
  public:
    bool isSymmetrical(TreeNode* root1, TreeNode* root2) {
        //节点都为空时，返回true
        if (root1 == nullptr && root2 == nullptr)
            return true;

        if (root1 == nullptr || root2 == nullptr || root1->val != root2->val)
            return false;
        
        return (isSymmetrical(root1->left, root2->right) &&
                isSymmetrical(root1->right, root2->left));
    }
    bool isSymmetrical(TreeNode* pRoot) {
        return isSymmetrical(pRoot, pRoot);
    }
};

方法二：辅助队列

一个对称的二叉树，两个不同方向的层间遍历一定是相同的。

通过创建两个辅助队列，对二叉树进行不同方向的层间遍历，进行比较。

时间复杂度：o(n)

空间复杂度：o(n)。两个辅助队列

class Solution {
  public:
    bool isSymmetrical(TreeNode* pRoot) {
        //空树为对称的
        if (pRoot == NULL)
            return true;
        //辅助队列用于从两边层次遍历
        queue<TreeNode*> q1;
        queue<TreeNode*> q2;
        q1.push(pRoot->left);
        q2.push(pRoot->right);
        while (!q1.empty() && !q2.empty()) {
            //分别从左边和右边弹出节点
            TreeNode* left = q1.front();
            q1.pop();
            TreeNode* right = q2.front();
            q2.pop();
            //都为空暂时对称
            if (left == NULL && right == NULL)
                continue;
            //某一个为空或者数字不相等则不对称
            if (left == NULL || right == NULL || left->val != right->val)
                return false;
            //从左往右加入队列
            q1.push(left->left);
            q1.push(left->right);
            //从右往左加入队列
            q2.push(right->right);
            q2.push(right->left);
        }
        //都检验完都是对称的
        return true;
    }
};