leetcode 101. 对称二叉树

题目描述

题目链接：leetcode 101. 对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

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

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

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

分析

画一棵层数较多的对称二叉树：
  可以发现一个规律：只要在相同的层数往不同的方向（一个往左另一个就往右）遍历，就会走出一条对称的路径。只有当所有对称的路径上的数值都对应相等时，二叉树才可能是对称二叉树。
请结合下图理解上面的规律（图中对称的路径“颜色相同”）。
对于“当前的根结点root”，只需要作以下几个判断：
（1）root的右儿子和左儿子是否相等。
（2）root的“右儿子的右儿子”和root的“左儿子的左儿子”是否相等。
（3）root的“右儿子的左儿子”和root的“左儿子的右儿子”是否相等。
只有(1)(2)(3)三种情况都判断为相等时，二叉树才可能是对称二叉树。
请结合下图理解：
继续往下判断时，应当把“右儿子的右儿子”和“左儿子的左儿子”视作同一个节点的左右儿子，把“右儿子的左儿子”和root的“左儿子的右儿子”视作同一个节点的左右儿子。实际上这就是“走对称路径”的过程。（结合下图理解）

由二叉树的递归结构和本问题中存在的“局部问题的相似性”，可以设计一个递归解法。

代码一

此代码较繁琐， 但是能很好地展现“由当前节点往下扩展两层的具体情况分类”。

/**
 * 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 check(TreeNode* l,TreeNode* r){
       if(l==nullptr&&r==nullptr) return true;
       if(l!=nullptr&&r==nullptr) return false;
       if(l==nullptr&&r!=nullptr) return false;
           if(l->val==r->val){   //(1)
               if(l->left!=nullptr&&r->right==nullptr)  return false;
               if(l->left==nullptr&&r->right!=nullptr)  return false;
               if(l->right!=nullptr&&r->left==nullptr)  return false;
               if(l->right==nullptr&&r->left!=nullptr)  return false;
               if(l->left==nullptr&&r->right==nullptr&&l->right==nullptr&&r->left==nullptr) return true;
               if(l->left==nullptr&&r->right==nullptr&&l->right!=nullptr&&r->left!=nullptr){  //(2)
                   if(l->right->val==r->left->val) {
                   return check(l->right,r->left);
                   }
                   return false;
               }  //(2)
               if(l->left!=nullptr&&r->right!=nullptr&&l->right==nullptr&&r->left==nullptr){ //(3)
                   if(l->left->val==r->right->val) {
                   return check(l->left,r->right);
                   }
                   return false;
               }    //(3)
               if(l->left!=nullptr&&r->right!=nullptr&&l->right!=nullptr&&r->left!=nullptr){  //(4)
                   if(l->left->val==r->right->val&&l->right->val==r->left->val) {
                   return check(l->right,r->left)&&check(l->left,r->right);
                   }
                   return false;
               } //(4)
               
            }   //(1)
          return false;
    }

    bool isSymmetric(TreeNode* root) {
    if(root==nullptr) return true;
    return check(root->left,root->right);
    }
};

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
51
52
53

代码二

参考官方题解，和上面其实是同一个思想。

/**
 * 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 check(TreeNode* l,TreeNode* r){
       if(l==nullptr&&r==nullptr) return true;
       if(l!=nullptr&&r==nullptr) return false;
       if(l==nullptr&&r!=nullptr) return false;
       return l->val==r->val&&check(l->left,r->right)&&check(l->right,r->left);
    }
    bool isSymmetric(TreeNode* root) {
    if(root==nullptr) return true;
    return check(root->left,root->right);
    }
};

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