leetcode_day15

本文最后更新于 2024年8月18日 上午

今日内容:

层序遍历

思路就是用队列记录逐层,这样顺序不会变。进入一层时最好记录队列初长度,然后根据长度遍历该层,避免根据队列是否空而判断该层是否遍历结束,便于即时将子节点入队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
vector<int> temp;
if(root == nullptr) return {};
TreeNode * cur = root;
queue<TreeNode*> q;
q.push(cur);
while(!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
cur = q.front();
q.pop();
temp.push_back(cur->val);
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
ans.push_back(temp);
temp.clear();
}
return ans;
}

翻转二叉树

递归版比较简单,太过简单,所以skip

迭代版就看作在遍历,而且是前序遍历那种单循环,出栈后把左右节点交换,然后压栈左右节点继续就行,给出循环部分的核心代码本来就是核心代码模式,又再核心……

1
2
3
4
5
6
7
while(!st.empty()) {
TreeNode* node = st.top(); // 中
st.pop();
swap(node->left, node->right);
if(node->right) st.push(node->right); // 右
if(node->left) st.push(node->left); // 左
}

对称二叉树

递归版很简单,写一个辅助函数判断左右节点是不是相等,是树就接着递归,然后从根开始对每一个分支节点的左右孩子判断就行
代码没写,偷了个懒😜

迭代版要难一点,仅限于手写层面,思路不难

迭代需要用队列或者栈等来存,但是不是按左右顺序挨个入队,而是左右对应交替入队,这样方便判断是否相等

下附carl的漂亮含注释代码,carl原文链接

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
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == NULL) return true;
queue<TreeNode*> que;
que.push(root->left); // 将左子树头结点加入队列
que.push(root->right); // 将右子树头结点加入队列

while (!que.empty()) { // 接下来就要判断这两个树是否相互翻转
TreeNode* leftNode = que.front(); que.pop();
TreeNode* rightNode = que.front(); que.pop();
if (!leftNode && !rightNode) { // 左节点为空、右节点为空,此时说明是对称的
continue;
}

// 左右一个节点不为空,或者都不为空但数值不相同,返回false
if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
return false;
}
que.push(leftNode->left); // 加入左节点左孩子
que.push(rightNode->right); // 加入右节点右孩子
que.push(leftNode->right); // 加入左节点右孩子
que.push(rightNode->left); // 加入右节点左孩子
}
return true;
}
};

leetcode_day15
https://novelyear.github.io/2024/06/05/leetcode-day15/
作者
Leoo Yann
更新于
2024年8月18日
许可协议