144. 二叉树的前序遍历
145. 二叉树的后序遍历
94. 二叉树的中序遍历
102. 二叉树的层序遍历
103. 二叉树的锯齿形层序遍历
589. N 叉树的前序遍历
590. N 叉树的后序遍历
429. N 叉树的层序遍历
这两天做了好多二叉树N叉树的各种遍历题，稍微总结一下。
概念
对于二叉树来说，前中后序遍历(pre, in, postorder, 记一下英文)分别代表根节点在遍历时的位置。前序就是根-左-右，中序左-右-根，后序左-根-右。
对于实际问题来说，需要记住考虑根节点为空的情况，可以先写一个判断，后面根据需要删除或者留着。
递归
这三种遍历方式都可以很快用递归来实现。直接写一个dfs，其中在结果中添加的顺序：前序最先添加，然后遍历左右节点。中序先遍历左节点，然后添加，然后遍历右节点。后序先遍历左右节点最后添加。实现都比较简单。代码逻辑同样可以推广到N叉树，具体实现除了左右节点变成N个子节点其他都一样。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
void preorder(TreeNode *root, vector<int> &res) {
if (root == nullptr) {
return;
}
res.push_back(root->val);
preorder(root->left, res);
preorder(root->right, res);
}
vector<int> preorderTraversal(TreeNode *root) {
vector<int> res;
preorder(root, res);
return res;
}
};
|
迭代
如果使用迭代的话，需要使用栈模拟一个DFS的过程，其中前序最简单，首先在栈中压入根节点，然后弹出根节点并按顺序（因为弹出的顺序与加入的顺序相反，需要先加入右节点再加入左节点）加入根节点。后序的话可以使用前序相反的顺序，其中仅需要将加入节点的顺序反过来，即先加入左节点然后右节点，这样从栈中弹出节点的顺序就是中-右-左，然后将输出的序列整个反向，就变成了左-右-中。
使用visited set记录访问状态：
这种方法是在做N叉树的后序遍历时候看到的，对于二叉树来说同样比较适用，同时也可以应用到二叉树的中序遍历中。
对于后序遍历和中序遍历来说，重要的是在遍历时何时弹出一个节点，如果一个节点是叶子结点，可以直接弹出。不是的话，如果是后序遍历，需要在弹出左右子节点后再弹出根节点，如果是中序遍历，需要在弹出左子节点后弹出根节点。于是可以使用一个额外的visited set记录节点访问的状态。
后序遍历
对于后序遍历，在每次访问栈顶的结点时，首先判断是否是叶子结点/是否在visited set中出现过，然后将其左右子节点加入并将根节点加入visited set。这样在访问完左右子节点后，下一个访问的根节点就一定已经被标记visited了，所以可以直接弹出并记录结果。具体代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| vector<int> postorderTraversal(TreeNode* root) {
vector<int>result;
if (!root) return result;
stack<TreeNode*>s;
set<TreeNode*>visited;
s.push(root);
while (!s.empty()) {
TreeNode* temp = s.top();
if (!temp -> left && !temp -> right || visited.count(temp)) {
result.push_back(temp -> val);
s.pop();
continue;
}
if (temp -> right) s.push(temp -> right);
if (temp -> left) s.push(temp -> left);
visited.insert(temp);
}
return result;
}
|
这种思路同样运用于N叉树。
中序遍历
对于中序遍历来说和后序遍历不一样，仅在根节点的左子节点被访问过后就可以弹出根节点了，所以首先将根节点从栈里取出来，把右子节点压入栈底，然后再把根节点压入，最后将子节点压入并将根节点标记为visited。左子节点被弹出后，下一个访问的是根节点（已经被标记为visited），而最后才是右子节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| vector<int> inorderTraversal(TreeNode* root) {
vector<int>result;
if (!root) return result;
stack<TreeNode*>s;
set<TreeNode*>visited;
s.push(root);
while (!s.empty()) {
TreeNode* temp = s.top();
if (!temp -> left && !temp -> right || visited.count(temp)) {
result.push_back(temp -> val);
s.pop();
continue;
}
s.pop();
if (temp -> right) s.push(temp -> right);
s.push(temp);
if (temp -> left) s.push(temp -> left);
visited.insert(temp);
}
return result;
}
|
层序遍历
层序遍历的话类似于一个BFS的过程，在代码中使用队列而不是栈。因为在每次遍历时，都会将本层的所有节点遍历一遍，然后弹出，压入下一层的所有节点，因此每次只需要访问队列中的所有结点就可以完成一层的遍历了。同样的思路可以运用于N叉树。
对于锯齿形遍历来说，只需要记录该层是奇数层还是偶数层，然后在对应的层上将结果反向就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>>result;
if (!root) return result;
queue<Node*>q;
q.push(root);
while (!q.empty()) {
vector<int>level;
int size = q.size();
for (int i = 0; i < size; i++) {
Node* temp = q.front();
if (temp -> children.size() > 0) {
for (auto child: temp -> children) {
q.push(child);
}
}
level.push_back(temp -> val);
q.pop();
}
result.push_back(level);
}
return result;
}
|
