史上最全遍历二叉树详解（C++模板）

vlambda
2020-11-21

史上最全遍历二叉树详解（C++模板）

首先要构造一个二叉树，这个能够方便我们对其了解。众所周知，二叉树遍历方式用前序遍历，中序遍历，后序遍历和层次遍历

每种遍历的方法还有不相同，前中后序遍历可以用迭代和递归完成，而层次遍历更多选择bfs（广度优先这种方法）作为一名学生，更加应该去掌握利用迭代方法

struct TreeNode{ int val; TreeNode* left; TreeNode* right;  TreeNode(int val1,TreeNode *l = nullptr,TreeNode *r = nullptr){//构造函数 val = val1; left = l; right = r; }};

一、利用递归遍历二叉树

因为是递归遍历，就不要过多的文字说明，这是因为比较常规，我尽量都会直接给出代码，而不会过度去说明。

1.1前序遍历（根节点-左子树-右子树）

定义preorder(root)表示当前遍历到root节点的答案。按照定义，我们只要首先将root节点的值加入答案，然后递归调用preorder(root.left)来遍历root节点的左子树，最后递归调用preorder(root.right)来遍历root节点的右子树即可，递归终止的条件为碰到空节点。

   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;    }

1.2中序遍历（左子树-根节点-右子树）

定义inorder(root) 表示当前遍历到root 节点的答案，那么按照定义，我们只要递归调用 inorder(root.left) 来遍历root节点的左子树，然后将root节点的值加入答案，再递归调用inorder(root.right) 来遍历root 节点的右子树即可，递归终止的条件为碰到空节点

 void inorder(TreeNode* root, vector<int>& res) { if (!root) { return; }        inorder(root->left, res);//这行跟之前有些不同 res.push_back(root->val); inorder(root->right, res); } vector<int> inorderTraversal(TreeNode* root) { vector<int> res; inorder(root, res); return res;}

1.3 后序（左子树-右子树-根节点）

定义postorder(root)表示当前遍历到root节点的答案。按照定义，我们只要递归调用postorder(root->left)来遍历root节点的左子树，然后递归调用postorder(root->right)来遍历 root节点的右子树，最后将root节点的值加入答案即可，递归终止的条件为碰到空节点。

 void postorder(TreeNode *root, vector<int> &res) { if (root == nullptr) { return; } postorder(root->left, res); postorder(root->right, res); res.push_back(root->val); } vector<int> postorderTraversal(TreeNode *root) { vector<int> res; postorder(root, res); return res;    }

4遍历的模板如下

 void 函数名(TreeNode *root, vector<int> &res) { if (root == nullptr) { return; } #后序遍历 函数名(root->left, res); 函数名(root->right, res); res.push_back(root->val); #中序遍历 函数名(root->left, res); res.push_back(root->val); 函数名(root->right, res);        #前序遍历 res.push_back(root->val); 函数名(root->left, res); 函数名(root->right, res); } vector<int> postorderTraversal(TreeNode *root) { vector<int> res; 函数名(root, res); return res;    }

二、利用迭代遍历

2.1前序

迭代算法，我看了那么多博主的文章，基本都是用栈，一方面也是比较好理解，另外一方面也比较好模板化。代码是重复性的，有规律的。只有认真去理解，才会便于自己去写代码和规范自己代码。

递归思路：先树根，然后左子树，然后右子树。每棵子树递归。在迭代算法中，思路演变成，每到一个节点 A，就应该立即访问它。因为，每棵子树都先访问其根节点。对节点的左右子树来说，也一定是先访问根。

栈S;

while(root|| S不空){

while(root){

将root节点的值放入res；

root压入S;

root = root=root->left;

}

root = 栈顶

s.pop();

root = root->right;

}

完整代码如下

 vector<int> preorderTraversal(TreeNode* root) { vector<int> res; if (root == nullptr) { return res;        } stack<TreeNode*> stk; while (!stk.empty() || root != nullptr) {            while (root != nullptr) {     //这一步是将root->left全部压入栈 res.push_back(root->val); //这个可以用emplace_back函数替代 stk.push(root); root = root->left; } root = stk.top(); stk.pop(); root = root->right; } return res; }

2.2中序

已知前序怎么去操作，那么对于中序来说那就变得更加简单；只是一个读取的顺序不一样而已。中前后到前中后，无非就是选择读取左结点和头节点的顺序。

vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> stk; while (root != nullptr || !stk.empty()) { while (root != nullptr) { stk.push(root); root = root->left; } root = stk.top(); stk.pop();            res.push_back(root->val);//跟前序的时候，就是讨论何时把结点放到数组中去 root = root->right; } return res;    }

2.3后序

后序主要跟中序的区别就是：头结点比较晚读取，那就要去思考，跟之前的方法是不是差不多，其中不同点在于那里。

难点判断是不是有右子树，如果有的话，我们就要把那个头结点压进入栈，然后在压入右节点。这样根绝栈的特性，我们就可以知道，先出来就是右结点然后就是做节点咯

 vector<int> postorderTraversal(TreeNode *root) { vector<int> res; if (root == nullptr) { return res;        } stack<TreeNode *> stk;        TreeNode *prev = nullptr;  //这个主要是来判断是否弹出过左结点 while (root != nullptr || !stk.empty()) { while (root != nullptr) { stk.push(root); root = root->left; } root = stk.top(); stk.pop(); if (root->right == nullptr || root->right == prev) {                res.push_back(root->val);// root->right == prev是为了压入头结点 prev = root;                root = nullptr;  // 为了防止重复压入左节点 } else { stk.push(root); root = root->right; } } return res;    }

后序的迭代相对来说比较难一点，网上还有另外一种解法（可以自行去了解，那种比较简单，利用了对称的原则）

2.4迭代模板

前序和中序:vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> stk; while (root != nullptr || !stk.empty()) { while (root != nullptr) {                // res.push_back(root->val); 放在着就是前序 stk.push(root); root = root->left; } root = stk.top(); stk.pop();            //  res.push_back(root->val); 放在着就是中序 root = root->right; } return res;    }

后序的模板基本就是靠理解咯

三、层次遍历

层次遍历采取的是bfs，这种比较常见，当然你也可以采取dfs，这种当然可以。我主要去介绍bfs，dfs这种稍微比较不常见。

 vector<vector<int>> levelOrder(TreeNode* root) { vector <vector <int>> ret; if (!root) { return ret; }
 queue <TreeNode*> q; q.push(root); while (!q.empty()) {            int currentLevelSize = q.size();  //这个很重要，如果没有这个，程序运行后会得到错误的结果 ret.push_back(vector <int> ()); for (int i = 1; i <= currentLevelSize; ++i) { auto node = q.front(); q.pop(); ret.back().push_back(node->val); if (node->left) q.push(node->left); if (node->right) q.push(node->right); }        }  return ret;    }