101. 对称二叉树

Posted on In , Views: Disqus:
LeetCode刷题系列。

描述

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

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

1
2
3
4
5
6

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

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

1
2
3
4
5
6
7

  1
 / \
2   2
 \   \
 3    3

说明:

如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

来源：力扣（LeetCode）
链接：101. Symmetric Tree

解题思路

本题一开始我的思路是这样的，要满足镜像对称，那么需要满足以下两个条件：

  • 左右孩子节点的值相同
  • 左右子树本身也都满足镜像对称

然后用递归写代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


bool isSymmetric(struct TreeNode* root)
{
    
    if(!root)
        return true;
     struct TreeNode* left = root->left;
    struct TreeNode* right = root->right;
    
    if(!left || !right)
        return false;
    return (left->val == right->val) && isSymmetric(left) && isSymmetric(right);   
}

提交的时候发现有bug，这个测试用例[1,2,2,3,4,4,3]过不去，显然，回过头来想前面的第二个条件太过于苛刻，其实镜像对称并不需要左右子树都是镜像对称，等价于下面的条件即可：

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

左右子树本身也都满足镜像对称是充分条件，但不是必要条件，每个树的右子树都与另一个树的左子树镜像对称才是充分条件。

根据这个逻辑很容易写出用递归的代码，具体见解法一。

当然，如果能够用递归实现，通常也是可以用迭代进行实现。

根据上面的分析，从对称的角度，比较直观的的想法就是利用层序遍历，看每一层的遍历结果是否对称。

考虑用一个队列来保存每层层序遍历的结果，入队的顺序依次为：左子树的左儿子，右子树的右儿子，左子树的右儿子，右子树的的左儿子。然后在出队的时候两两检查是不是对称。

具体代码见解法二。

解法二只用到了一个队列，其实用两个队列也可以。大致过程与解法二相同，只是将左子树和右子树的值分布压入不同的队列，然后分别逐个弹出进行比较，需要注意压入的顺序需要对应起来，即将左子树的左子结点和右子结点排入队列1，将右子树的右子结点和左子结点排入队列2。

具体代码见解法三。

代码

解法一

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


//辅助函数
bool isMirrorTree(struct TreeNode* p, struct TreeNode* q)
{
    if(!p && !q)
        return true;
    if(!p || !q)
        return false;
    return (p->val == q->val) && isMirrorTree(p->right, q->left) && isMirrorTree(p->left, q->right);
}

bool isSymmetric(struct TreeNode* root)
{
    
    return isMirrorTree(root,root);
}


解法二

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * 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) 
    {
        //判断root是否为空，为空返回true
        if(!root) return true;
        //初始化TreeNode指针队列
        queue<TreeNode*> q;
        
        //向队列压入根节点的左右儿子
        q.push(root->left);
        q.push(root->right);
        
        //层序遍历二叉树并列举各种不满足对称条件的情况返回
        while(!q.empty())
        {
            TreeNode* left = q.front();
            q.pop();
            TreeNode* right = q.front();
            q.pop();
            
            //碰到叶子节点
            if(!left && !right) continue;
            // 其中一个为null 返回false
            if(!left || !right) return false;
            // 值不相同 返回false
            if(left->val != right->val) return false;
            
            //按照顺序入列
            q.push(left->left);
            q.push(right->right);
            q.push(left->right);
            q.push(right->left);
            
        }
        //跳出循环后若未返回返回true
        return true;      
    }
};

解法三

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * 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) 
    {
        //判断root是否为空，为空返回true
        if (!root) return true;
        
        //队列初始化
        queue<TreeNode*> q1, q2;
        
        //分别向两个压入root的左右节点
        q1.push(root->left);
        q2.push(root->right);
        
        //层序遍历二叉树并列举各种不满足对称条件的情况返回
        while (!q1.empty() && !q2.empty()) 
        {
            TreeNode* left = q1.front(); 
            q1.pop();
            TreeNode* right = q2.front(); 
            q2.pop();
            
            if (!left && !right) continue;
            
            if((left && !right) || (!left && right)) 
                return false;
                
            if (left->val != right->val) 
                return false;
            
            q1.push(left->left);
            q1.push(left->right);
            
            q2.push(right->right);
            q2.push(right->left);
        }
        return true;
    }
};

参考