欢迎访问LeetCode题解合集

题目描述

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

题解：

判断两棵树是否互为镜像，需要满足以下两个条件：

• 两棵树的根节点值相等
• 第一棵树的左子树和第二棵树的右子树互为镜像，第一棵树的右子树和第二棵树的左子树互为镜像

可以 递归 或者 迭代 实现。

对左子树使用 先序遍历 ，对右子树使用 逆先序遍历 。

时间复杂度：$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 dfs( TreeNode *p, TreeNode *q ) {
        if ( !p && !q ) return true;
        if ( !p || !q || p->val != q->val ) return false;
        if ( !dfs( p->left, q->right ) ) return false;
        if ( !dfs( p->right, q->left ) ) return false;
        return true;
    }
    bool isSymmetric(TreeNode* root) {
        if ( !root ) return true;
        return dfs( root->left, root->right );
    }
};
/*
时间：4ms，击败：84.91%
内存：15.9MB，击败：14.89%
*/

迭代版本：

/**
 * 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;
        TreeNode *p = root->left, *q = root->right;
        stack<TreeNode*> stk;
        while ( p || q || stk.size() ) {
            while ( p && q ) {
                if ( p->val != q->val ) return false;
                stk.push( p );
                stk.push( q );
                p = p->left;
                q = q->right;
            }
            if ( p || q ) return false;
            q = stk.top(); stk.pop();
            p = stk.top(); stk.pop();
            p = p->right, q = q->left;
        }
        return true;
    }
};
/*
时间：0ms，击败：100.00%
内存：16MB，击败：9.62%
*/