关注公众号:高性能架构摸索。后盾回复【材料】，能够收费支付
俗话说：学如逆水行舟,逆水行舟;心似平原走马,易放难收。这句话对程序员而言，领会更深。这行曾经越来越卷了，时刻筹备着，。
二叉树，在面试中，已是必备的开胃菜。而在二叉树相干的面试题目中，遍历更是常考题目。本文将从二叉树的遍历角度动手，从递归和非递归角度来剖析和解说二叉树的遍历。
遍历
二叉树的遍历是指从根节点登程，依照某种秩序顺次拜访二叉树中的所有节点，使每个节点被且仅被拜访一次。
二叉树的遍历，有先序遍历、中序遍历以及后续遍历三种。
下面三种遍历形式中的先序、中序以及后序三种形式，是父节点绝对于子节点来说的。如果父节点先于子节点，那么就是先序遍历。如果子节点先于父节点，那么就是后序遍历。而对于子节点来说，如果先左节点，而后是父节点，而后再是右节点，那么就是中序遍历。
如【图一】所示二叉树。其三种遍历后果如下：
先序遍历: A->B->D->E->C->F->G
中序遍历: D->B->E->A->F->C->G
后续遍历: D->E->B->F->G->C->A
为了便于了解代码，咱们先定义下树的节点定义：
struct TreeNode { TreeNode *left; TreeNode *right; int val;};先序遍历
定义：先拜访父节点，而后遍历左子树，最初遍历右子树。
递归
置信递归遍历大家都会很容易写进去，且bugfree。因为实现代码很简略。
在上图【图二】中，应用递归遍历，就是将其左子树和右子树也当做一棵树来进行解决。代码如下：
void PreOrder(TreeNode *root) { if (!root) { return; } // 遍历根节点(此处仅为输入，读者也能够依据理论须要进行解决，比方存储等) std::cout << root->val << std::endl; // 遍历左子树 PreOrder(root->left); // 遍历右子树 PreOrder(root->right);}非递归
在非递归操作中，咱们依然是依照先拜访根节点，而后遍历左子树，接着遍历右子树的形式。
- 达到节点A,拜访节点A,开始遍历A的左子树
- 达到节点B，拜访节点B，开始遍历B的左子树
达到节点D,拜访节点D,因为节点D无子树，因而节点D遍历实现
- 节点D遍历实现，意味着节点B的左子树遍历实现，因而接着遍历节点B的右子树
达到节点E，拜访节点E。因为节点E无子树，因而节点E遍历实现
- 节点E遍历实现，意味着节点B的右子树遍历实现，也预示着节点B的子树遍历实现
- 开始遍历节点A的右子树
- 达到节点C，拜访节点C。开始遍历C的左子树
达到节点F，拜访节点F。因为节点F无子树，因而节点F遍历实现
- 节点F遍历实现，意味着节点C的左子树遍历实现，因而开始遍历节点C的右子树
到的节点G，拜访节点G。因为节点G无子树，因而节点G遍历实现
- 节点G遍历实现，意味着节点C的右子树遍历实现，进而预示着节点C遍历实现
- 节点C遍历实现，意味着节点A的右子树遍历实现，进而意味着节点A遍历实现，因而以A为根节点的树遍历实现。
用非递归形式遍历二叉树，须要引入额定的数据结构栈(stack),其根本流程如下：
1、申请一个栈stack，而后将头节点压入stack中。
2、从stack中弹出栈顶节点，打印
3、将其右孩子节点（不为空的话）先压入stack中
4、将其左孩子节点（不为空的话）压入stack中。
5、一直反复步骤2、3、4，直到stack为空，全副过程完结。
代码如下：
void PreOrder(TreeNode *root) { if (!root) { return; } std::stack<TreeNode*> s; s.push(root); // 步骤1 while (!s.empty()) { auto t = s.top(); s.pop();//出栈 std::cout << t->val << std::endl; // 拜访节点 if (t->right) { s.push(t->right); // 对应步骤3 } if (t->left) { s.push(t->left); // 对应步骤4 } }}中序遍历
定义：先遍历左子树，拜访根节点，遍历右子树
递归
在上图【图四】中，应用递归遍历，就是将其左子树和右子树也当做一棵树来进行解决。代码如下：
void InOrder(TreeNode *root) { if (!root) { return; } // 遍历左子树 InOrder(root->left); // 遍历根节点(此处仅为输入，读者也能够依据理论须要进行解决，比方存储等) std::cout << root->val << std::endl; // 遍历右子树 InOrder(root->right);}上述中序遍历的递归代码，相比于先序遍历，只是将拜访根节点的行为放在了遍历左右子树之间。
非递归
在非递归操作中，咱们依然是依照先遍历左子树，而后拜访根节点，最初遍历右子树的形式。
- 达到节点A，节点A有左子树，遍历节点A的左子树
- 达到节点B，节点B有左子树，遍历节点B的左子树
达到节点D，节点D无子树，拜访D节点
- 因为D无子树，意味着B的左子树遍历实现，那么就回到B节点
- 拜访B节点，遍历B节点的右子树
达到节点E，节点E无子树，拜访节点E
- E节点遍历实现，意味着以B为根的子树遍历实现，回到A节点
- 达到A节点，拜访A节点，遍历A节点的右子树
- 达到C节点，遍历C节点的左子树
达到F节点，因为F节点无子树，因而拜访F节点。
- 因为F节点无子树，意味着C节点的左子树遍历实现，回到C节点
- 达到C节点，拜访C节点，遍历C的右子树
达到节点G，因为G无子树，因为拜访节点G
- G节点遍历实现，意味着C节点的右子树遍历实现，进而意味着A节点的右子树遍历实现，从意味着以A节点为根的二叉树遍历实现。
中序遍历，同样须要额定的辅助数据结构栈。
- 将根节点放入栈
2、如果根节点有左子树，则将左子树的根节点放入栈
3、反复步骤1和2.持续遍历左子树
4、从栈中弹出节点，进行拜访，而后遍历右子树(反复步骤1和2)
5、如果栈为空，则遍历实现
代码如下：
void InOrder(TreeNode *root) { if (!root) { return; } std::stack<TreeNode*> s; auto p = root; while (!s.empty() || p) { if (p) { // 步骤1和2 s.push(p); p = p->left; } else { // 步骤4 auto t = s.top(); std::cout << t->val << std::endl; p = t->right; } }}后续遍历
定义：先遍历左子树，再遍历右子树，最初拜访根节点
递归
void PostOrder(TreeNode *root) { if (!root) { return; } // 遍历左子树 PostOrder(root->left); // 遍历右子树 PostOrder(root->right); // 遍历根节点(此处仅为输入，读者也能够依据理论须要进行解决，比方存储等) std::cout << root->val << std::endl;}下面就是后续遍历的递归写法，比拟写先序遍历、中序遍历以及后续遍历三者的递归遍历写法，大部分代码是一样的，惟一的区别就是拜访根节点的代码地位不一样：
先序遍历：先拜访根节点，而后遍历左子树，最初遍历右子树
中序遍历：先遍历左子树，而后拜访根节点，最初遍历右子树
后序遍历：先遍历左子树，而后遍历右子树，最初拜访根节点
非递归
在非递归操作中，咱们依然是依照先遍历左子树，而后拜访根节点，最初遍历右子树的形式。
- 达到节点A，遍历A的左子树
- 达到节点B，遍历B的左子树
达到节点D，因为D无子树，则拜访节点D
- 节点D无子树，意味着节点B的左子树遍历实现，接着遍历B的右子树
达到节点E，因为E无子树，则拜访节点E
- 节点E无子树，意味着节点B的右子树遍历实现，接回到节点B
- 拜访节点B，回到节点B的根节点A
- 达到节点A，拜访节点A的右子树
- 达到节点C，遍历节点C的左子树
达到节点F，因为节点F无子树，因而拜访节点F
- 节点F拜访实现，意味着C节点的左子树遍历实现，因而回到节点C
- 达到节点C，遍历节点C的右子树
达到节点G，因为节点G无子树，因为拜访节点G
- 节点G拜访实现，意味着C节点的右子树遍历实现，回到节点C
达到节点C，拜访节点C
- 节点C遍历实现，意味着节点A的右子树遍历实现，回到节点A
- 节点A的右子树遍历实现，拜访节点A
用非递归形式遍历二叉树，须要引入额定的数据结构栈(stack),其根本流程如下：
1、申请两个栈stack，而后将头节点压入指定stack中。
2、从stack中弹出栈顶节点，放入另外一个栈中
3、将其左孩子节点（不为空的话）先压入stack中
4、将其右孩子节点（不为空的话）压入stack中。
5、一直反复步骤2、3、4，直到stack为空。
6、反复拜访另外一个栈，直至栈空
void PostOrder(TreeNode *root) { if (!root) { return; } std::stack<TreeNode*> s1; std::stack<TreeNode*> s2; s1.push(root); while (!s1.empty()) { auto t = s1.top(); s1.pop(); s2.push(t); if (t->left) { s1.push(t->left); } if (t->right) { s1.push(t->right); } } while (!s2.empty()) { auto t = s2.top(); s2.pop(); std::cout << t->val << std::endl; }}结语
对于二叉树来说，所谓的遍历，是指沿着某条路线顺次拜访每个节点，且均只做一次拜访。二叉树的遍历，是面试中常面算法之一，肯定要把其弄懂，必要的时候，须要背诵，乃至做到肌肉记忆。