101. 对称二叉树

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

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

Solution1（递归版）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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) {
        return isMirror(root, root);
    }
    
    bool isMirror(TreeNode* t1, TreeNode* t2){
        //都为NULL
        if(!t1 && !t2) return true;
        //有一个结点为NULL，另一个不为NULL
        if(!t1 || !t2) return false;
        return (t1->val == t2->val) && isMirror(t1->left, t2->right)
            && isMirror(t1->right, t2->left);
    }
};

看的官方题解。

把一棵对称树分成左子树和右子树。

如果左子树和右子树对称，则该数相同。

扩展到一般概念就是：

  • 有两棵树。
  • 两棵树的根节点相同。
  • 每个树的右子树都与另一个树的左子树镜像对称。

翻译为递推公式就是：

1
2
3
4
TreeNode* t1,t2;
t1->val == t2->val;
t1->left == t2->right;
t1->right = t2->left;

结束条件为两棵树为空。

整理可得上述代码。

Solution2（迭代版）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 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) {
        queue<TreeNode*> q;
        q.push(root);
        q.push(root);
        while(!q.empty()){
            TreeNode* t1 = q.front(); q.pop();
            TreeNode* t2 = q.front(); q.pop();
            if(!t1 && !t2) continue;
            if(!t1 || !t2) return false;
            if(t1->val != t2->val) return false;
            q.push(t1->left);
            q.push(t2->right);
            q.push(t2->left);
            q.push(t1->right);
            
        }
        return true;
    }
};

翻译为了迭代版，只不过根本的思想是一样的。都是将一棵树化为两棵树来进行判断的。

Solution3（中序迭代版）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 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*> lefts,rights;
        TreeNode* l = root->left;
        TreeNode* r = root->right;
        while(l || r || lefts.size()){
            while(l && r){
                lefts.push(l),l = l->left;
                rights.push(r), r = r->right;
            }
            if(l || r) return false;
            l = lefts.top();lefts.pop();
            r = rights.top(); rights.pop();
            if(l->val != r->val) return false;
            l = l->right,r = r->left;
        }
        return true;
    }
};