心之所向便是光

Leetcode 101.对称二叉树

  • 2021-06-23
  • 作者 Ender
  • 1.92K 字
  • 次阅读

题目描述：

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

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

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

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

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

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

链接：

https://leetcode-cn.com/problems/symmetric-tree

题目分析

1.递归

  什么样的树是镜像对称的？对应的结点值相同，并且他们的左右子树也刚好对称。这个定义是递归的，因此我们可以使用一个递归函数 check 来检查两个树是否对称。结点同时为空则对称，若同时不为空，则需满足结点值相同，并且左右子树互相对称。而我们只需要检查根结点的左右子树是否满足这样的对称树即可。这样的遍历是前序遍历。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    bool check(TreeNode* p, TreeNode* q){
        if(!p && !q) return true;
        if(!p || !q) return false;
        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
    }
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return check(root->left, root->right);
    }
};

  时间复杂度：$O(n)$，其中 $n$ 为二叉树的结点数。我们遍历了二叉树。
  空间复杂度：$O(n)$，其中 $n$ 为二叉树的结点数。也即栈空间的最大深度。

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
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        queue<TreeNode*> que;
        que.push(root->left);
        que.push(root->right);
        while(!que.empty()){
            TreeNode* p = que.front();
            que.pop();
            TreeNode *q = que.front();
            que.pop();

            if(!p && !q) continue;
            if(!p || !q || p->val != q->val) return false;

            que.push(p->left);
            que.push(q->right);

            que.push(p->right);
            que.push(q->left);
        }
        return true;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 为二叉树的结点数。我们遍历了二叉树。每个结点最多进队一次，出队一次。
  空间复杂度：$O(n)$，其中 $n$ 为二叉树的结点数。队列的最大长度为 $n$。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
, , , ,
最后编辑：2021-06-23