目录

题目描述：

解题思路：

C++

python

---

题目描述：

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

例如，二叉树 [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

解题思路：

 递归法。查看左右子树情况，有三种情况：

（1）左右子树都为空，返回true；

（2）左右子树其中一个为空，或者都不为空但顶点值不等，返回false；

（3）都不为空，且顶点值相等，则判断左子树的左节点和右子树的右节点是否对称，且判断左子树的右节点和右子树的左节点是否对称。

C++

执行用时：8 ms, 在所有 C++ 提交中击败了34.54%的用户

内存消耗：15.9 MB, 在所有 C++ 提交中击败了85.35%的用户

通过测试用例：197 / 197

/**
 * 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) {
        // 因为判断是否对称，需要对比左子树的左节点和右子树的右节点是否相等，左子树的右节点和右子树的左节点是否相等，
        // 所以每次需要传入左右两个节点。
        return isMirror(root->left, root->right);
        
    }
    bool isMirror(TreeNode* l_root, TreeNode* r_root)
    {
        // 当前左右节点为空返回true
        if (l_root == nullptr && r_root == nullptr) return true;
        
        // 左右节点一个为空，一个不为空返回false，或者都不为空，但值不同也是返回false
        if (l_root == nullptr && r_root != nullptr) return false;
        if (l_root != nullptr && r_root == nullptr) return false;
        if (l_root != nullptr && r_root != nullptr && l_root->val != r_root->val) return false;
        
        // 左右子树都不空，且值相等，则递归。
        // 对比左子树的左节点和右子树的右节点是否相等，左子树的右节点和右子树的左节点是否相等
        else{
            return isMirror(l_root->left, r_root->right) && isMirror(l_root->right, r_root->left);
        }
    }
};

迭代法：

利用栈，入栈出栈顺序：

迭代依次入两个，出两个, 再比较两个是否相等

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

入栈顺序：1 2 2 3 3 4 4

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true; // 为空
        
        stack<TreeNode *> s; // 栈中存放指针
        TreeNode *p = root->left, *q = root->right; // 用p,q两个指针遍历树
        s.push(p); // 依次入栈2个
        s.push(q); 
        
        while(!s.empty()){ // 栈不空
            p = s.top(); s.pop(); // 依次出栈2个
            q = s.top(); s.pop();
            
            if (!p && !q) continue; // 都为空
            if (!p || !q) return false; // 其中一个为空
            if (p->val != q->val) return false; // 都不为空，但值不等
            
            else{ // 都不为空，但值相等
                s.push(p->left); s.push(q->right);  // 入栈：左子树的左节点，右子树的右节点
                s.push(p->right); s.push(q->left);  // 入栈：左子树的右节点，右子树的左节点
            }
        }
        
        return true;
    }
};

python

执行用时：16 ms, 在所有 Python 提交中击败了90.22%的用户

内存消耗：13.1 MB, 在所有 Python 提交中击败了86.29%的用户

通过测试用例：197 / 197

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.isMirror(root.left, root.right)
    
    def isMirror(self, r1, r2):
        # 1 一个为空，一个不为空，则返回false
        if r1 is None and r2 is not None: return False
        if r1 is not None and r2 is None: return False
        # 2 都为空，则返回true
        if r1 is None and r2 is None: return True
        # 3 都不为空，不相等返回true
        if r1 is not None and r2 is not None and r1.val != r2.val:
            return False
        else:  # 相等，再看看其他节点是否对称
            return self.isMirror(r1.left, r2.right) and self.isMirror(r1.right, r2.left)