文章目录
LeetCode【学习计划】:【数据结构】
102. 二叉树的层序遍历
LeetCode: 102. 二叉树的层序遍历
中 等 \color{#FFB800}{中等} 中等
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
示例:
二叉树:[3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
返回其层序遍历结果:
[
[3],
[9,20],
[15,7]
]
方法1:广度优先搜索
我们只需要一层一层地遍历树即可。广度优先搜索需要队列来完成,而队列中元素的变化是有一定规律的:
- 第
i
层的结点出队; - 存入第
i
层所有结点的孩子结点,也就是存入了第i+1
层的结点。
可以发现每次队列中的元素总是一层一层地变化。这一层的结点全部拿出来,放入下一层的结点。由此我们可以在拿之前定义一个变量 n
来存放队列的长度。
一开始,队列中只有第 i
层的结点,因此 n
就是第 i
层的结点数。然后循环 n
次,每次从队列中拿出一个结点,并存入它的孩子结点。由于我们记录了每一层的结点数,所以不会从队列中多拿。
在代码中,首先将根结点入队。外层循环的条件是队列不为空,每一次外层循环对应一层。而内层循环是将当前层的结点取出,并放入孩子结点。
#include <vector>
#include <queue>
using namespace std;
class Solution
{
public:
vector<vector<int>> levelOrder(TreeNode *root)
{
if (!root)
return {};
queue<TreeNode *> queue;
vector<vector<int>> ans;
queue.push(root);
while (!queue.empty())
{
int n = queue.size();
vector<int> inner;
inner.reserve(n);
for (int i = 0; i < n; i++)
{
TreeNode *p = queue.front();
queue.pop();
inner.emplace_back(p->val);
if (p->left)
queue.push(p->left);
if (p->right)
queue.push(p->right);
}
ans.emplace_back(inner);
}
return ans;
}
};
复杂度分析
-
时间复杂度: O ( n ) O(n) O(n)
-
空间复杂度: O ( 1 ) O(1) O(1)。我们只需要常量空间来存储若干变量。
参考结果
Accepted
34/34 cases passed (4 ms)
Your runtime beats 72.33 % of cpp submissions
Your memory usage beats 63.63 % of cpp submissions (12.2 MB)
104. 二叉树的最大深度
LeetCode: 104. 二叉树的最大深度
简 单 \color{#00AF9B}{简单} 简单
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
方法1:深度优先搜索(递归)
假设我们从递归中知道了左子树和右子树各自的最大深度,那么当前根结点的最大深度即为左子树和右子树深度的最大值+1。
在递归的尽头,传入的必然会是空指针。因此若传入为空指针,返回 0
。
#include <vector>
using namespace std;
class Solution
{
public:
int maxDepth(TreeNode *root)
{
if (root == nullptr)
return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
复杂度分析
-
时间复杂度: O ( n ) O(n) O(n)。
n
为树的结点数,树中的每个结点都会被遍历一次。 -
空间复杂度: O ( h e i g h t ) O(height) O(height)。
height
为树的深度,主要为递归的栈空间开销。
参考结果
Accepted
39/39 cases passed (8 ms)
Your runtime beats 69.23 % of cpp submissions
Your memory usage beats 92.72 % of cpp submissions (18.3 MB)
方法2:广度优先搜索
与上文中 102. 二叉树的层序遍历 一题类似,我们可以在每次对层进行扩展时,记录当时队列的长度。外层循环就是对第 i
层的扩展,因此第 i
层的深度即为 i
(本题中树的深度从 1
开始计数)。
#include <vector>
#include <queue>
using namespace std;
class Solution
{
public:
int maxDepth(TreeNode *root)
{
if (!root)
return 0;
queue<TreeNode *> queue;
int level = 0;
queue.push(root);
while (!queue.empty())
{
int n = queue.size();
for (int i = 0; i < n; i++)
{
TreeNode *p = queue.front();
queue.pop();
if (p->left)
queue.push(p->left);
if (p->right)
queue.push(p->right);
}
level++;
}
return level;
}
};
复杂度分析
-
时间复杂度: O ( n ) O(n) O(n)
-
空间复杂度: O ( n ) O(n) O(n)。这个方法的空间消耗取决于队列中元素的数量,最坏情况下达到 O ( n ) O(n) O(n)。
参考结果
Accepted
39/39 cases passed (8 ms)
Your runtime beats 69.23 % of cpp submissions
Your memory usage beats 12.33 % of cpp submissions (18.5 MB)
101. 对称二叉树
LeetCode: 101. 对称二叉树
简 单 \color{#00AF9B}{简单} 简单
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [1,2,2,3,4,4,3]
是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3]
则不是镜像对称的:
1
/ \
2 2
\ \
3 3
进阶:
你可以运用递归和迭代两种方法解决这个问题吗?
方法1:双指针 + 深度优先搜索(递归)
一个树是镜像对称的话,也就是左子树和右子树对称。所以我们可以从2棵树在什么条件下镜像对称来入手,共有以下2个条件:
- 根结点的值相等。
- 每棵树的右子树和另一棵树的左子树镜像对称,反之同理。
我们可以采用双指针的思想和深度优先相结合的方法来完成这道题。在整棵树的根节点的左右孩子上各设置一个指针,2个指针按深度优先去遍历左子树和右子树。左侧的指针如果向左孩子走,右侧的指针就像右孩子走,反之亦然。
在深度优先的过程中,如果两个结点的值不同则不对称;如果一侧有结点,另一侧没有结点,也是不对称。
class Solution
{
public:
bool isSymmetric(TreeNode *root)
{
return doublePointer(root->left, root->right);
}
bool doublePointer(TreeNode *p, TreeNode *q)
{
if (!p && !q)
return true;
if (!p || !q)
return false;
return p->val == q->val && doublePointer(p->left, q->right) && doublePointer(p->right, q->left);
}
};
复杂度分析
-
时间复杂度: O ( n ) O(n) O(n)
-
空间复杂度: O ( n ) O(n) O(n)
参考结果
Accepted
197/197 cases passed (4 ms)
Your runtime beats 79.83 % of cpp submissions
Your memory usage beats 93.2 % of cpp submissions (15.8 MB)
方法2:双指针 + 迭代
这个方法中,我们需要用到队列。
一开始,我们将根结点的左右孩子入队。每次取的时候,从队列中取出2个结点并比较它们的值。在将该两个结点的孩子结点入队时,也要对称地入队。
#include <queue>
using namespace std;
class Solution
{
public:
bool isSymmetric(TreeNode *root)
{
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 ) O(n) O(n)
-
空间复杂度: O ( n ) O(n) O(n)
参考结果
Accepted
197/197 cases passed (8 ms)
Your runtime beats 37.67 % of cpp submissions
Your memory usage beats 13.64 % of cpp submissions (16.2 MB)