题目描述

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

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

题目分析

题目可以用递归和递推两种方法解决, 递归方法思路如下:

对根节点下两棵子树进行判断, 两棵子树的根节点值相等并且子树的两颗子树也为对称则为对称树.

源码(递归)

class Solution {
public:
    bool isTwoSym(TreeNode* l, TreeNode* r) {
        if(l == NULL || r == NULL) { // 两个节点中含有NULL节点
            return l == r;
        }else {
            return l->val == r->val && isTwoSym(l->left, r->right) && isTwoSym(l->right, r->left);
        }
    }
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return true;
        if(root->left == NULL && root->right == NULL) return true;
        // ↑ 单根节点情况
        if((root->left == NULL && root->right != NULL) || (root->right == NULL && root->left != NULL)) return false;
        // ↑ 根节点下只有一个节点情况
        return isTwoSym(root->left, root->right);
    }
};

源码(深度优先搜索)

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return true; // 如果根节点是空节点则返回true
        stack<TreeNode*> st1, st2; // 将节点储存在栈中
        st1.push(root->left); // 将根节点左右的节点压入栈中
        st2.push(root->right);
        while(!st1.empty() && !st2.empty()) { // 在任意一个栈为空时停止循环
            TreeNode* cur1 = st1.top();
            TreeNode* cur2 = st2.top();
            st1.pop();
            st2.pop();
            if((cur1 == NULL && cur2 != NULL) || (cur1 != NULL && cur2 == NULL)) return false;
            if(cur1 != NULL) {
                if(cur1->val != cur2->val) return false;
                st1.push(cur1->left); // 左节点先压入左 后压入右
                st1.push(cur1->right);
                st2.push(cur2->right); // 右节点先压入右 后压入左
                st2.push(cur2->left);
            }
        }
        return true;
    }
};