复习一下二叉树的遍历，把力扣相关的题再做一遍，记录一下各种遍历的C++实现方法。

文章目录

前言1. 前序遍历1.1 前序遍历递归实现1.2 前序遍历迭代实现 2. 中序遍历2.1 中序遍历递归实现2.2 中序遍历迭代实现 3. 后序遍历3.1 后序遍历递归实现3.2 后序遍历迭代实现 4. 层序遍历4.1 层序遍历递归实现4.2 层序遍历迭代实现

前言

    首先明确二叉树节点的定义，就是力扣题给出的：

struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };

    返回也按照对应的力扣题用vector了。

1. 前序遍历

    前序遍历就是父节点在前面啦，“父-左-右”要不就是“父-右-左”，题目规定是前者，因此这里还是用“父-左-右”吧。对应的力扣题为Leetcode144。

1.1 前序遍历递归实现

    递归方法很简单，其实就是最简单的深度优先搜索。

vector<int> res; vector<int> preorderTraversal(TreeNode* root) { if(root) { res.push_back(root->val); preorderTraversal(root->left); preorderTraversal(root->right); } return res; }

1.2 前序遍历迭代实现

    递归其实隐式地用到了栈，要是不用递归实现前序遍历，可以显式地用一个辅助栈。

vector<int> preorderTraversal(TreeNode *root) { vector<int> res; stack < TreeNode * > S;//辅助栈 TreeNode *node = root; while (!S.empty() || node != nullptr) { while (node != nullptr) { S.push(node); res.push_back(node->val); node = node->left; } node = S.top()->right; S.pop(); } return res; }

2. 中序遍历

    中序遍历就是父节点在中间，如按照“左-父-右”的顺序遍历二叉树。对应的力扣题为Leetcode94。

2.1 中序遍历递归实现

    递归方法还是一样的简洁，和前序遍历相比就是记录节点值的时刻换了。

vector<int> res; vector<int> inorderTraversal(TreeNode* root) { if(root) { inorderTraversal(root->left); res.push_back(root->val); inorderTraversal(root->right); } return res; }

2.2 中序遍历迭代实现

    和前序遍历的代码差不多，无非就是前序是在入栈的时候记录节点的值，而中序是在出栈的时候记录节点的值。

vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack <TreeNode *> S;//辅助栈 TreeNode *node = root; while (!S.empty() || node != nullptr) { while (node != nullptr) { S.push(node); node = node->left; } res.push_back(S.top() -> val); node = S.top() -> right; S.pop(); } return res; }

3. 后序遍历

    后序遍历就是父放在最后了，“左-右-父”。对应的力扣题为Leetcode145。

3.1 后序遍历递归实现

    不解释。

vector<int> res; vector<int> postorderTraversal(TreeNode* root) { if(root){ postorderTraversal(root->left); postorderTraversal(root->right); res.push_back(root->val); } return res; }

3.2 后序遍历迭代实现

    还是有点生疏，到这里卡住了一会，就想到可以用先序遍历（注意是“父-右-左”），然后逆过来。但这样有些讨巧，虽然也把题给做了，这里先记录下这种方法。

vector<int> postorderTraversal(TreeNode* root) { vector<int> res; stack <TreeNode *> S;//辅助栈 TreeNode *node = root; while (!S.empty() || node != nullptr) { while (node != nullptr) { S.push(node); res.push_back(S.top() -> val); node = node->right; } node = S.top() -> left; S.pop(); } reverse(res.begin(), res.end()); return res; }

    还是感觉这个方法太讨巧了，所以想找别的方法。因此在题解中搜寻，看到一种有意思的方法，这里也记录下来。直接给出原址：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/a-li-mian-shi-ti-zhi-yong-zhan-qu-zuo-er-cha-shu-d/.。这种方法大意是在父节点入栈后再压入一个nullptr作为指示，具体还是看代码好懂。顺带一提，看了巧妙的解法我都不敢写下去了，感觉自己还是差远了，没必要做这个笔记，但是为复习，还是继续写。

2020-9-29更新：今天的力扣每日一题就是这个，官方答案给出的迭代方法很厉害。一种方法是如果root的右儿子不为空，或不是已经遍历了的节点，就再放回去，遍历完右子树的节点再遍历root。另外一种方法用到Morris遍历，Morris遍历我现在还不能参透。

4. 层序遍历

    层序遍历，顾名思义就是一层一层地遍历，对应的力扣题为Leetcode102。

4.1 层序遍历递归实现

    感觉层序遍历还是用迭代方法好想一些，如果非要递归也不是不行。一种讨巧的方法是在递归的同时计算层数，然后将节点值放到准确的位置。但这种方法也只能用来做这个题了，和翻转先序的结果以解决后序遍历问题一样，个人感觉这种方法也不算真的在“层序”。

vector<vector<int>> res; void dfs(TreeNode* node, int level){ if(node){ if(level >= res.size()) res.push_back(vector<int>()); res[level].push_back(node -> val); dfs(node -> left, level + 1); dfs(node -> right, level + 1); } } vector<vector<int>> levelOrder(TreeNode* root) { dfs(root, 0); return res; }

    再次提醒自己遇到层序遍历还是用迭代吧！

4.2 层序遍历迭代实现

    层序遍历就不用stack了，用C++的queue（队列）辅助实现，用到是思想是广度优先搜索（BFS）。

vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> res; queue<TreeNode*> Q;//辅助队列 if(root) Q.push(root); while(!Q.empty()){ vector<int> tmp; int N = Q.size(); for(int i = 0; i < N; ++i){ TreeNode* node = Q.front(); tmp.push_back(node -> val); if(node -> left) Q.push(node -> left); if(node -> right) Q.push(node -> right); Q.pop(); } res.push_back(tmp); } return res; }

注：好了，就这样了，如果有什么问题，或者说之后想到什么可以改进的地方，那就之后复习再修改吧。