博客

给你一个二叉树的根节点 root ， 检查它是否轴对称。

解法一：递归

如果一个树的左子树与右子树镜像对称，那么这个树是对称的。

因此，该问题可以转化为：两个树在什么情况下互为镜像？

如果同时满足下面的条件，两个树互为镜像：

• 它们的两个根结点具有相同的值

• 每个树的右子树都与另一个树的左子树镜像对称，每个树的左子树也与另一个树的右子树镜像对称。

上述两个条件表明：两个树如果对称，首先根节点的值要相同，其次除了根节点的其他子树也要镜像，因此这里要用到子树之间是否是镜像的结果，因此递归函数要用到返回值bool。

我们可以实现这样一个递归函数，通过「

同步移动」两个指针

的方法来遍历这棵树，p和q，每次检查当前 pp 和 qq 节点的值是否相等，如果相等再判断左右子树是否对称。

class Solution {
public:
    bool check(TreeNode* node1, TreeNode* node2){
        //都为空
        if(!node1 && !node2) return true;
        //有一个不为空
        if((!node1 && node2) || (node1 && !node2)) return false;
        //都不为空，但是val不同
        if(node1->val != node2->val)  return false;
        //都不为空，但是val相同，还要看这两棵树是否是镜像的，要分别看外侧和内侧
        bool outside = check(node1->left, node2->right);
        bool inside = check(node1->right, node2->left);
        return outside && inside;
    }

    bool isSymmetric(TreeNode* root) {
        if(!root)return true;
        return check(root->left, root->right);
    }
};

时间复杂度：每个节点都访问了一次，因此O(n)。

空间复杂度：和递归的深度相关，每个节点都会递归一次，因此是O(n)。

解法二：迭代

两个根节点的值是否相同

一个节点的左和另一个节点的右，一个节点的右和另一个节点的左相同。

下面是用栈的实现：

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;

        stack<TreeNode*> st;
        st.push(root->left);
        st.push(root->right);

        while(st.size()){
            TreeNode* node1 = st.top();
            st.pop();
            TreeNode* node2 = st.top();
            st.pop();
            
            if(!node1 && !node2) continue;
            if((!node1 && node2) || (node1 && !node2)) return false;
            if(node1->val != node2->val) return false;
            st.push(node1->left);
            st.push(node2->right);
            st.push(node1->right);
            st.push(node2->left);
        }

        return true;
    }
};

时间复杂度：每个节点会被访问一次，O(n)。

空间复杂度：最多不会超过n个节点，O(n)。