LeetCode

LeetCode-对称的二叉树

判断一棵二叉树是否是对称的，例子如下。左边数是一个对称二叉树，而右边不是：

1
2
3
4
5
    5               5
   / \             / \
  4   4           5   5
 /\   /\         /\   /
7 8   8 7       5 5  5

思路

对于左边的树，既然对称那么遍历顺序root->l->r与root->r->l得到的节点序列是相同的。均为{5,4,7,8,4,8,7}，而对于右边的非对称树，两种遍历序列也是相同的。所以此方法不可行，而且还用到额外的存储空间。

但是如果将遍历到的空结点也放入序列中，就可以了。不过下面的实现，使用online方法，避免二外空间的使用。

实现

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
/**
 * 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 symetric(root, root);
    }
    
    bool symetric(TreeNode* root1, TreeNode* root2){
        
        // 都为空：
        if (root1==nullptr && root2==nullptr) return true;
        // 只有一个为空：
        if (root1==nullptr || root2==nullptr) return false;
        // 都不为空，但值不相等
        if (root1->val != root2->val) return false;
        
        // 值相等： 
        // 则继续判断 root1->左==root2->右 && root1->右==root2->左
        return symetric(root1->left, root2->right) && 
                symetric(root1->right, root2->left);
    }
};

体会这里完备的表达式：

1
2
3
4
5
6
// 都为空：
if (root1==nullptr && root2==nullptr) return true;
// 只有一个为空：
if (root1==nullptr || root2==nullptr) return false;
// 都不为空，但值不相等
if (root1->val != root2->val) return false;

neat！！