LeetCode【学习计划】:【数据结构】
LeetCode: 102. 二叉树的层序遍历
中 等 \color{#FFB800}{中等} 中等
给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。
示例:
二叉树:[3,9,20,null,null,15,7]
,
3 / \ 9 20 / \ 15 7
返回其层序遍历结果:
[ [3], [9,20], [15,7] ]
我们只需要一层一层地遍历树即可。广度优先搜索需要队列来完成,而队列中元素的变化是有一定规律的:
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)
LeetCode: 104. 二叉树的最大深度
简 单 \color{#00AF9B}{简单} 简单
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7]
,
3 / \ 9 20 / \ 15 7
返回它的最大深度 3 。
假设我们从递归中知道了左子树和右子树各自的最大深度,那么当前根结点的最大深度即为左子树和右子树深度的最大值+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)
与上文中 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)
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
进阶:
你可以运用递归和迭代两种方法解决这个问题吗?
一个树是镜像对称的话,也就是左子树和右子树对称。所以我们可以从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个结点并比较它们的值。在将该两个结点的孩子结点入队时,也要对称地入队。
#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)