树的遍历是一个老生常谈的话题，常见的遍历方法无非就是前序遍历、中序遍历、后序遍历以及层次遍历，如下图所示。其中前三种遍历可以基于深度优先搜索实现，而层次遍历基于广度优先搜索实现。本文主要讨论二叉树的各种遍历问题及其变体，这些方法很容易扩展到多叉树的情形，因此不再赘述。
如果没有特殊说明，本文中的树节点都按照如下方式定义：
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
前序、中序和后序遍历
前、中、后序遍历的递归实现非常简单，我们这里就不讨论了。这一小节我们主要关注如何使用迭代的方式实现这三种遍历方式。
LeetCode 144. 二叉树的前序遍历
前序遍历按照根节点、左子树、右子树的顺序对二叉树进行访问。因此，我们可以将根节点压入栈中，然后在每次迭代中弹出当前的栈顶元素，并将其子节点压入栈中（注意要先压入右子节点再压入左子节点）最终的输出顺序就是前序遍历的顺序。
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> stk;
vector<int> order;
if (root == nullptr) return order;
stk.push(root);
while (stk.size()) {
auto pval = stk.top();
stk.pop();
order.push_back(pval->val);
if (pval->right) stk.push(pval->right);
if (pval->left) stk.push(pval->left);
}
return order;
}
};
LeetCode 94. 二叉树的中序遍历
中序遍历按照左子树、根节点、右子树的顺序访问二叉树。因此，我们在访问根节点时，要保证根节点的左子树已经遍历完成。在实现上，我们先把根节点压入栈中，然后再把根节点的左子树压入栈中，每次迭代弹出栈顶元素。等到左子树和根节点全都遍历完成后，我们再把右子树压入栈中。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> stk;
vector<int> order;
auto node = root;
while (node || stk.size()) {
while (node) {
stk.push(node);
node = node->left;
}
node = stk.top();
stk.pop();
order.push_back(node->val);
node = node->right;
}
return order;
}
};
LeetCode 145. 二叉树的后序遍历
后序遍历的顺序是左子树、右子树、根节点，即先遍历左子树，再遍历右子树，最后访问根节点。在将某个节点的值加入到序列中时，我们需要确认该节点的左子树和右子树都已经完成遍历。在具体实现上，我们需要为每个节点保存一个状态信息，用来判断该节点的右子树是否已经被遍历过。如果没有遍历右子树，我们就把右子树压入栈中，否则弹出栈顶元素并将该节点的值加入到结果序列中。
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
using Pair = pair<TreeNode*, bool>;
vector<int> order;
stack<Pair> stk;
auto node = root;
while (node || stk.size()) {
while (node) {
stk.emplace(node, false);
node = node->left;
}
auto& curr = stk.top();
if (curr.second) {
stk.pop();
order.push_back(curr.first->val);
} else {
node = curr.first->right;
curr.second = true;
}
}
return order;
}
};
相似题目：
LeetCode 589. N叉树的前序遍历
LeetCode 590. N叉树的后序遍历
根据遍历序列还原树
有一类问题是根据遍历序列重构二叉树，这类问题的解题思路就是利用分治法，不断地将序列分成两部分，利用这两部分分别重构左子树和右子树。以LeetCode 105. 从前序与中序遍历序列构造二叉树为例，我们需要根据前序遍历和中序遍历序列，重新构造二叉树。我们知道，前序遍历序列中，第一个值一定是树的根节点。然后，我们在中序遍历的序列中查找根节点的位置，将中序遍历序列分成两部分，这两个子序列分别是左子树和右子树的中序遍历序列。此时，我们已经知道了左子树和右子树的中序遍历序列的长度，而一棵树的中序遍历和前序遍历的序列长度是一样的，因此，我们可以根据序列长度，在前序遍历序列中分别找到左子树和右子树的前序遍历序列。这时，我们就可以分别构建左子树和右子树了。
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.size() == 0 || inorder.size() == 0) return nullptr;
int root_val = *(preorder.cbegin());
auto root_it = find(inorder.begin(), inorder.end(), root_val);
if (root_it == inorder.end()) return nullptr;
int dis = distance(inorder.begin(), root_it);
vector<int> left_preorder(preorder.begin()+1, preorder.begin()+dis+1);
vector<int> right_preorder(preorder.begin()+dis+1, preorder.end());
vector<int> left_inorder(inorder.begin(), root_it);
vector<int> right_inorder(root_it+1, inorder.end());
TreeNode* root = new TreeNode(root_val);
root->left = buildTree(left_preorder, left_inorder);
root->right = buildTree(right_preorder, right_inorder);
return root;
}
};
相似题目：
LeetCode 106. 从中序与后序遍历序列构造二叉树
层次遍历
LeetCode 102. 二叉树的层次遍历
层次遍历就是按照每一层对树进行遍历，先遍历第一层，再遍历第二层……层次遍历实现起来非常简单，就是利用队列存储每次访问的节点以及该节点的深度。当节点出队时，将该节点的所有子节点入队，并把深度增加1，直到队列中没有元素为止。
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
using Pair = pair<int, TreeNode*>;
queue<Pair> que;
vector<vector<int>> ans;
que.emplace(0,root);
while(que.size()){
auto p = que.front();
que.pop();
if(p.second){
if(ans.size() == p.first) ans.emplace_back();
ans.at(p.first).push_back(p.second->val);
que.emplace(p.first+1, p.second->left);
que.emplace(p.first+1, p.second->right);
}
}
return ans;
}
};
LeetCode 297. 二叉树的序列化与反序列化
首先生成二叉树的层序遍历结果，然后根据层序遍历恢复原来的二叉树结构。
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string data = "[";
queue<TreeNode*> que;
que.push(root);
while (que.size()) {
auto node = que.front();
que.pop();
if (node) {
data += to_string(node->val);
que.push(node->left);
que.push(node->right);
} else {
data += "null";
}
data.push_back(',');
}
*data.rbegin() = ']';
return data;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
vector<TreeNode*> vec;
int sign = 1;
int num = 0;
for (int i = 1;i < data.size();++i) {
if (data[i] == ',' || i == data.size() - 1) {
vec.push_back(new TreeNode(sign * num));
num = 0;
sign = 1;
} else if (data[i] == 'n') {
vec.push_back(nullptr);
i += 4;
} else if (isdigit(data[i])) {
num = 10 * num + (data[i] - '0');
} else if (data[i] == '-') {
sign = -1;
}
}
TreeNode* root = vec.size() ? vec[0] : nullptr;
queue<TreeNode*> que;
que.push(root);
for (int i = 1;i < vec.size(); i+= 2) {
auto node = que.front();
que.pop();
auto left = vec[i];
auto right = vec[i+1];
if (left) {
node->left = left;
que.push(left);
}
if (right) {
node->right = right;
que.push(right);
}
}
return root;
}
};
相似题目：
LeetCode 103. 二叉树的锯齿形层次遍历
LeetCode 107. 二叉树的层次遍历 II
LeetCode 199. 二叉树的右视图
LeetCode 429. N叉树的层次遍历