LeetCode 101. 对称二叉树

递归法

递归三部曲

1. 确定递归函数的参数和返回值

因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。返回值自然是bool类型

bool compare(TreeNode* l, TreeNode* r)
1

2. 确定终止条件

要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。

节点为空的情况有：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）

• 左节点为空，右节点不为空，不对称，return false
• 左不为空，右为空，不对称 return false
• 左右都为空，对称，返回true

此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：左右都不为空，比较节点数值，不相同就return false

if (l == NULL && r != NULL) return false;
if (l != NULL && r == NULL) return false;
if (l == NULL && r == NULL) return true;
// 排除了空节点，再排除数值不相同的情况
if (l->val != r->val) return false;
1
2
3
4
5

此时左右节点不为空，且数值也不相同的情况我们也处理了。最后就要处理左右节点都不空，且值相等的情况，这需要继续向下递归的compare，用左节点的左孩子和右节点的右孩子比较，用左节点的右孩子和右节点的左孩子比较

3. 确定单层递归的逻辑

此时才进入单层递归的逻辑，单层递归的逻辑就是处理 左右节点都不为空，且数值相同的情况。

比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子
比较内测是否对称：传入左节点的右孩子，右节点的左孩子

如果左右都对称就返回true ，有一侧不对称就返回false

代码如下：

bool outside = compare(l->left, r->right);
bool inside = compare(l->right, r->left);
return outside && inside;
1
2
3

完整代码如下：

class Solution {
public:
    bool compare(TreeNode* l, TreeNode* r) {
        // 首先排除空节点的情况
        if (l == NULL && r != NULL) return false;
        if (l != NULL && r == NULL) return false;
        if (l == NULL && r == NULL) return true;
        // 排除了空节点，再排除数值不相同的情况
        if (l->val != r->val) return false;

        // 此时就是：左右节点都不为空，且数值相同的情况
        // 此时才做递归，做下一层的判断
        bool outside = compare(l->left, r->right);
        bool inside = compare(l->right, r->left);
        return outside && inside;
    }
    
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(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

精简版如下：

class Solution {
public:
    // compare用于比较l和r节点是否相同
    bool compare(TreeNode* l, TreeNode* r){
        if(nullptr == l && nullptr == r){
            return true; // 处理l和r都空
        }
        // 往下执行，l和r必然有非空的，如果发现有空的，则肯定不对称
        if(nullptr == l || nullptr == r){
            return false;  // 处理l和r只有一个空
        }
        // 再往下执行，l和r必然都不空
        return l->val == r->val && compare(l->left, r->right) && compare(l->right, r->left);
    }

    bool isSymmetric(TreeNode* root) {
        if(nullptr == root){
            return true;
        }
        return compare(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

迭代法

迭代法，其实是把左右两个子树要比较的元素顺序放进一个容器，然后成对成对的取出来进行比较

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == nullptr){
            return true;
        }
        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);

        while(!q.empty()){
        	// 取出比较的时候，需要成对取出比较
            TreeNode* l = q.front();
            q.pop();
            TreeNode* r = q.front();
            q.pop();
            if(l == nullptr && r == nullptr){
                continue;
            }
            if (l == nullptr || r == nullptr || l->val != r->val) return false;
			
			// push的时候，保证需要比较的两个节点相邻
            q.push(l->left);
            q.push(r->right);
            q.push(l->right);
            q.push(r->left);
        }
        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