摘要
- 二叉树的递归遍历对应着DFS，二叉树的层序遍历对应着BFS
- 层序遍历的迭代法实现一般用队列进行实现
LeetCode102 二叉树的层序遍历
- 这和教材上的层序遍历有所不同，题目要求我们区分树每一层。
- 树的第
k层的节点数最多为个，不过层序遍历并不是遍历完全二叉树，所以每层的个数应该由我们手动控制。
- 实现思路：
- 用
size记录当前层的节点个数，每从队列中弹出一个当前层的节点，size就减一，当size为零时，当前层遍历完成。
- 用
初见题目时完整的题解代码如下
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) {
return res;
}
queue<TreeNode*> que;
que.push(root);
int size = que.size();
int level = 0;
res.push_back({});
while (!que.empty()) {
if (que.front()) {
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
res[level].push_back(que.front()->val);
}
que.pop();
size--;
if (size == 0 && !que.empty()) {
size = que.size();
level++;
res.push_back({});
}
}
return res;
}
};
看了讲解之后，以上的方法虽然逻辑是对的，但是由于每次循环只处理一个节点，多了很多不必要的
size个数的判断，所以还可以改良。可以在循环内添加一个
for循环，每次循环直接遍历完一层
完整的题解代码如下
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
if (root) {
que.push(root);
}
vector<vector<int>> res;
while (!que.empty()) {
int size = que.size();
vector<int> level;
for (int i = 0; i < size; i++) {
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
level.push_back(que.front()->val);
que.pop();
}
res.push_back(level);
}
return res;
}
};
LeetCode107 二叉树的层序遍历II
- 将上一题的答案数组反转即可
- 有DFS的方法，日后补充
完整的题解代码如下
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
queue<TreeNode*> que;
if (root) {
que.push(root);
}
vector<vector<int>> res;
while (!que.empty()) {
int size = que.size();
vector<int> level;
for (int i = 0; i < size; i++) {
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
level.push_back(que.front()->val);
que.pop();
}
res.push_back(level);
}
reverse(res.begin(), res.end());
return res;
}
};
LeetCode199 二叉树的右视图
- 取每层的最后一个节点的值放入答案数组
完整的题解代码如下
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
queue<TreeNode*> que;
if (root) {
que.push(root);
}
vector<int> res;
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
if (i == size - 1) res.push_back(que.front()->val);
que.pop();
}
}
return res;
}
};
LeetCode637 二叉树的层平均值
完整题解代码如下
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
queue<TreeNode*> que;
if (root) que.push(root);
vector<double> res;
while (!que.empty()) {
int size = que.size();
double average = 0;
for (int i = 0; i < size; i++) {
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
average += que.front()->val;
que.pop();
}
average /= size;
res.push_back(average);
}
return res;
}
};
LeetCode429 N叉树的层序遍历
- 只需要修改每层遍历的逻辑，将添加左孩子和右孩子进队列扩展为添加N个孩子进队列
N叉树的节点定义
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
完整题解代码如下
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
queue<Node*> que;
if (root) que.push(root);
vector<vector<int>> res;
while (!que.empty()) {
int size = que.size();
vector<int> level;
for (int i = 0; i < size; i++) {
for (auto& iter : que.front()->children) {
if (iter) que.push(iter);
}
level.push_back(que.front()->val);
que.pop();
}
res.push_back(level);
}
return res;
}
};
LeetCode515 在每个树行中找最大值
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
queue<TreeNode*> que;
if (root) que.push(root);
vector<int> res;
while (!que.empty()) {
int size = que.size();
int maxVal = INT_MIN;
for (int i = 0; i < size; i++) {
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
maxVal = maxVal > que.front()->val ? maxVal : que.front()->val;
que.pop();
}
res.push_back(maxVal);
}
return res;
}
};
LeetCode116 填充每个节点的下一个右侧节点指针
完整题解代码如下
class Solution {
public:
Node* connect(Node* root) {
queue<Node*> que;
if (root) que.push(root);
while (!que.empty()) {
int size = que.size();
for (int i = 0;i < size; i++) {
Node* cur = que.front();
que.pop();
// 每层的最后一个节点的next为nullptr
Node* next = i == size - 1 ? nullptr : que.front();
cur->next = next;
if (cur->left) que.push(cur->left);
if (cur->right) que.push(cur->right);
}
}
return root;
}
};
LeetCode117 填充每个节点的下一个右侧节点指针
- 由于116的题解其实已经考虑了非完全二叉树的情况，所以题解代码相同
class Solution {
public:
Node* connect(Node* root) {
queue<Node*> que;
if (root) que.push(root);
while (!que.empty()) {
int size = que.size();
for (int i = 0;i < size; i++) {
Node* cur = que.front();
que.pop();
// 每层的最后一个节点的next为nullptr
Node* next = i == size - 1 ? nullptr : que.front();
cur->next = next;
if (cur->left) que.push(cur->left);
if (cur->right) que.push(cur->right);
}
}
return root;
}
};
LeetCode104 二叉树的最大深度
完整题解代码如下
class Solution {
public:
int maxDepth(TreeNode* root) {
queue<TreeNode*> que;
if (root) que.push(root);
int res = 0;
while (!que.empty()) {
int size = que.size();
res++;
for (int i = 0; i < size; i++) {
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
que.pop();
}
}
return res;
}
};
LeetCode111 二叉树的最小深度
- 根据最小深度的定义，当遍历到一个左右孩子都为空的节点时，即可直接返回当前节点所在的层数
class Solution {
public:
int minDepth(TreeNode* root) {
queue<TreeNode*> que;
if (root) que.push(root);
int res = 0;
while (!que.empty()) {
int size = que.size();
res++;
for (int i = 0; i < size; i++) {
if (!que.front()->left && !que.front()->right) {
return res;
}
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
que.pop();
}
}
return res;
}
};
LeetCode226 翻转二叉树
怎么理解翻转？翻转后的二叉树与原来的二叉树是镜面对称的，实际上就是交换每个节点的左孩子和右孩子。
- image.png
二叉树的遍历中，有前序、中序、后序、层序四种方式，都能访问到二叉树的所有节点。选择哪一种呢？
在这道题目里，只有中序是不太合适的，或者说逻辑上会有陷阱。先看前序遍历，代码如下
递归法，前序遍历
class Solution {
public:
void invertTreeWorkPlace(TreeNode* cur) {
if (cur == nullptr) {
return;
}
swap(cur->left, cur->right);
invertTreeWorkPlace(cur->left);
invertTreeWorkPlace(cur->right);
}
TreeNode* invertTree(TreeNode* root) {
invertTreeWorkPlace(root);
return root;
}
};
那中序遍历是不是把swap(cur->left, cur->right)下移一行就可以了呢？
class Solution {
public:
void invertTreeWorkPlace(TreeNode* cur) {
if (cur == nullptr) {
return;
}
invertTreeWorkPlace(cur->left);
swap(cur->left, cur->right); // 这合理吗？
invertTreeWorkPlace(cur->right);
}
TreeNode* invertTree(TreeNode* root) {
invertTreeWorkPlace(root);
return root;
}
};
我们自己模拟一次递归的过程就知道问题出在哪了
- 以LeetCode的示例1为例，一直递归调用直到节点1，
image.png
- 节点一为叶节点，所以
invertTreeWorkPlace(cur->left)直接返回；swap(cur->left, cur->right)实践上交换了两个nullptr；invertTreeWorkPlace(cur->right)也直接返回 - 返回到节点2，节点2执行
swap(cur->left, cur->right)
image.png
- 然后再执行
invertTreeWorkPlace(cur->right)，问题就来了，这时候的右子树是原来的左子树，实际上按这样的代码我们一直都在操作原来的二叉树的左子树。这就是中序遍历在操作节点时的逻辑陷阱。
一定要用中序遍历的话，就要注意此时要操作原来右子树就是要操作交换后的左子树。
class Solution {
public:
void invertTreeWorkPlace(TreeNode* cur) {
if (cur == nullptr) {
return;
}
invertTreeWorkPlace(cur->left);
swap(cur->left, cur->right);
invertTreeWorkPlace(cur->left);
}
TreeNode* invertTree(TreeNode* root) {
invertTreeWorkPlace(root);
return root;
}
};
统一形式的迭代法实现，用函数指针提高代码复用
class Solution {
public:
static void preorder(TreeNode* cur, stack<TreeNode*>& st) {
st.pop();
if (cur->right) st.push(cur->right);
if (cur->left) st.push(cur->left);
st.push(cur);
st.push(nullptr);
}
static void swapLeftAndRight(TreeNode* cur) {
swap(cur->left, cur->right);
}
void treeTraversal(TreeNode* root,
void (*traversal)(TreeNode* cur, stack<TreeNode*>& st),
void (*handle)(TreeNode* cur))
{
stack<TreeNode*> st;
if (root) st.push(root);
while (!st.empty()) {
TreeNode* cur = st.top();
if (cur) {
traversal(cur, st);
}
else {
st.pop();
cur = st.top();
st.pop();
handle(cur);
}
}
}
TreeNode* invertTree(TreeNode* root) {
treeTraversal(root, preorder, swapLeftAndRight);
return root;
}
};
LeetCode101 对称二叉树
- 这道题和 LeetCode226 类似，不过这里我们要做的是比较根节点的左右子树是否镜面对称，所以要同时访问两棵树。
- 要先判断当前节点的左右子树是否镜面对称，所以采用后序遍历的“左右中”，访问完左右子树后才能确定当前节点是否为一个对称二叉树的根节点。
- 先采用递归法实现：
- 确定递归函数的参数和返回值：要比较左右子树是否镜面对称，所以需要传入左子树和右子树的根节点；比较结果有对称和不对称两种，为布尔值，所以返回类型为布尔值。
-
确定递归的终止条件：
- 左子树为空，右子树不为空；自然是不对称的，返回false
- 左子树不为空，右子树为空；同1
- 左右子树都为空，说明这是一个叶节点，左右子树都为空自然对称，返回true
- 确定单层递归的逻辑：通过布尔运算实现，首先判断左子树的左子树是否和右子树的右子树相等；再判断左子树的右子树是否和右子树的左子树相等；最后再判断当前节点的左孩子是否和右孩子相等。
递归法实现的完整代码
class Solution {
public:
bool isSymmetricWorkPlace(TreeNode* left, TreeNode* right) {
if (!left && right) return false;
if (left && !right) return false;
if (!left && !right) return true;
bool res = true;
res = res && isSymmetricWorkPlace(left->left, right->right);
res = res && isSymmetricWorkPlace(left->right, right->left);
res = res && left->val == right->val;
return res;
}
bool isSymmetric(TreeNode* root) {
if (!root) return true;
return isSymmetricWorkPlace(root->left, root->right);
}
};
- 另外可以通过迭代法来判断树的每层是否镜面对称，但要记得每层的
nullptr也要进入队列来在层序中区分左孩子和右孩子 - 注意，每次比较的不是某个节点的左孩子和右孩子，而是某层的最左未被比较的节点和最右未被比较的节点。
以LeetCode的示例1为例
- 首先比较队列头和队列尾，此时的队列
[2, 2]
image.png
- 然后队列头和队列尾都出队。按镜面对称让队列头的左孩子、右孩子和队列尾的左孩子、孩子入队，此时的队列
[3, 4, 4, 3]
image.png
- 继续上述步骤，队列头和队列尾出队，二者左右孩子按镜面对称入队
- 此时队列
[nullptr, nullptr, 4, 4, nullptr, nullptr]
- 此时队列
- 循环直至队列为空，注意这不是层序遍历，并不是比较完一层再到下一层。
采用双端队列迭代法来实现判断二叉树是否对称
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root) {
deque<TreeNode*> deq;
deq.push_front(root->left);
deq.push_back(root->right);
while (!deq.empty()) {
TreeNode* left = deq.front();
deq.pop_front();
TreeNode* right = deq.back();
deq.pop_back();
// 左右子树都为空自然是对称的
if (!left && !right) {
continue;
}
// 这里是短路判断，只有要比较的左右两个节点都不为空才会比较值，防止操作空指针
if (!left || !right || (left->val != right->val)) {
return false;
}
// 用双端队列更加直观的体现出对称，其实也可以用普通队列实现
deq.push_front(left->right);
deq.push_front(left->left);
deq.push_back(right->left);
deq.push_back(right->right);
}
}
return true;
}
};
- 那用真正的层序遍历是否可以做这道题呢？当然是可以的，同样也要注意往每层的序列中加入
nullptr来区分左孩子和右孩子。 - 但是层序遍历有一个问题，就是我们要遍历完这一层后才能判断当前层是否镜面对称，相当于要多花一倍的时间。为了便于对比，在这里还是给出用层序遍历的实现代码。
层序遍历的实现代码
class Solution {
public:
bool isSymmetric(TreeNode* root) {
bool res = true;
if (!root) return res;
queue<TreeNode*> que;
if (root) que.push(root);
while (!que.empty()) {
int size = que.size();
vector<TreeNode*> level;
for (int i = 0; i < size; i++) {
if (que.front()) {
que.push(que.front()->left);
que.push(que.front()->right);
}
level.push_back(que.front());
que.pop();
}
if (level.size() > 1 && level.size() % 2) return false;
for (int i = 0, j = level.size() - 1; i < j; i++, j--) {
if (!level[i] && !level[j]) continue;
if (!level[i] || !level[j] || level[i]->val != level[j]->val) {
return false;
}
}
}
return res;
}
};
