二叉树遍历
image.png
前序遍历（根->左->右）
A->B->D->E->C->F
【递归实现】
class Solution {
public:
void preorder(TreeNode *node, vector<int> &res) {
if (node == nullptr) {
return;
}
res.push_back(node->val);
dfs(node->left, res);
dfs(node->right, res);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
dfs(root, res);
return res;
}
};
【迭代实现】
顺着指向左子节点的指针向下移动时，前序遍历将遍历遇到的每个节点并将它添加在栈中。
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
TreeNode *cur = root;
if (cur == nullptr) {
return res;
}
stack<TreeNode *>stack;
while(cur != nullptr || !stack.empty()) {
// 左子树一直入栈
while (cur != nullptr) {
// 保存结果
res.push_back(cur->val);
stack.push(cur);
cur = cur->left;
}
// 获取栈顶元素
cur = stack.top();
// 出栈
stack.pop();
// 右子树
cur = cur->right;
}
return res;
}
};
中序遍历（左->根->右）
D->B->E->A->F->C
【递归实现】
class Solution {
public:
void dfs(TreeNode *node, vector<int> &res) {
if (node == nullptr) {
return;
}
dfs(node->left, res);
res.push_back(node->val);
dfs(node->right, res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
dfs(root, res);
return res;
}
};
【迭代实现】
二叉树的遍历总是从根节点开始的，但当第1次到达根节点时，并不是马上遍历根节点，而是顺着指向左子节点的指针向下直到叶节点，也就是找到第1个真正被遍历的节点。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
TreeNode *cur = root;
if (cur == nullptr) {
return res;
}
stack<TreeNode *>stack;
while (cur != nullptr || !stack.empty()) {
// 左子树一直入栈
while (cur != nullptr) {
stack.push(cur);
cur = cur->left;
}
// 左子树已经到底
if (!stack.empty()) {
// 栈不空，获取栈顶元素
cur = stack.top();
// 出栈
stack.pop();
// 保存结果
res.push_back(cur->val);
// 右子树
cur = cur->right;
}
}
return res;
}
};
后序遍历（左->右->根）
D->E->B->F->C->A
【递归实现】
class Solution {
public:
void dfs(TreeNode *node, vector<int> &res) {
if (node == nullptr) {
return;
}
dfs(node->left, res);
dfs(node->right, res);
res.push_back(node->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
dfs(root, res);
return res;
}
};
【迭代实现】
当达到某个节点时，如果之前还没有遍历过它的右子树就得前往它的右子节点，如果之前已经遍历过它的右子树那么就可以遍历这个节。
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
TreeNode *cur = root;
if (root == nullptr) {
return res;
}
stack<TreeNode *> stack;
TreeNode *prev = nullptr;
while (cur != nullptr || !stack.empty()) {
// 左子树一直入栈
while (cur != nullptr) {
stack.push(cur);
cur = cur->left;
}
// 获取栈顶元素
cur = stack.top();
// 右子树为空 || 右子树等于前一个结点
if (cur->right == nullptr || cur->right == prev) {
// 出栈
stack.pop();
// 保存结果
res.push_back(cur->val);
prev = cur;
cur = nullptr;
} else {
cur = cur->right;
}
}
return res;
}
};
分层遍历
A->B->C->D->E->F
队列经常被用来实现二叉树的广度优先搜索。首先将二叉树的根节点插入队列。然后每次从队列中取出一个节点遍历。如果该节点有子节点，则将子节点插入队列。重复这个过程，直到队列被清空，此时二叉树所有的节点都已经遍历完。
如果需要区分二叉树不同的层，那么至少有两种方法可以实现。
- 第一种方法是用两个变量来表示当前层和下一层节点的数目。如果当前遍历的层的节点数目变成0，那么这一层所有的节点都已经遍历完，可以开始遍历下一层的节点。
- 第二种方法是用两个队列分别存放当前层和下一层的节点。如果当前层对应的队列被清空，那么该层所有的节点就已经被遍历完，可以开始遍历下一层。
【迭代实现】
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (root == nullptr) {
return res;
}
queue<TreeNode *> q;
// 根节点入队列
q.push(root);
while (!q.empty()) {
// 当前层的大小
int currLevelSize = q.size();
// 保存结果
res.push_back(vector<int> ());
// 获取队列的元素
for (int i = 1; i <= currLevelSize; i++) {
// 获取队头元素
auto node = q.front();
// 出队
q.pop();
// 向量的最后一个
res.back().push_back(node->val);
// 左子树
if (node->left != nullptr) {
q.push(node->left);
}
// 右子树
if (node->right != nullptr) {
q.push(node->right);
}
}
}
return res;
}
};
