summary : 面试中经常会让你写出三种遍历中的一种的非递归版本，通常是中序遍历和后序遍历，前序 遍历很少，因为前序遍历毕竟比较简单。 以我的智商，没有做过的话，只能想出来前序遍历的非递归版本，而中序遍历和后序遍历则 是绞尽脑汁都想不出来。最终参考了别人的做法，才理解并写出来了，算是记忆，估计再过 一段时间我又忘了。不过到时可以翻开我的这篇文章看看。 前序遍历 这个是最简单的。用一个栈存储节点，先输出栈顶元素的值，再把左右孩子的节点入栈（如 果有的话）。由于在遍历的时候是先遍历左子树再遍历右子树，那么反过来，在入栈的时候， 就先把右孩子入栈，再把左孩子入栈。 中序遍历 有难度。得先从...

summary : 这是我去人人面试的时候遇到的题，当时我写出来健壮性不好，立马就被刷了。 题目 给出两个单链表，升序排序好了，要求合并两个链表，合并之后还是升序排序，而且去重。 链表的节点结构如下： struct Node { : int value; struct Node \*next; }; 分析 没啥好分析，合并加去重，关键是要注意很多特殊情况，要写多一些测试用例。这里，我 用的是递归的方式实现，每次取得两个链表比较之后的头节点，并放到合并之后的链表的 后面。 我的代码 ::: {.code-include lexer="cpp"} ./merge...

summary : 这是一个很老很老的题，我做它，就是为了练习，练到能闭着眼睛在纸上写出来。 题目 输入某二叉树的前序遍历和中序遍历的结果，重新建立这棵二叉树，输出它的后序遍历。 假设不含重复数字，类型为int。 分析 根据前序遍历和中序遍历求后序遍历是经典的二叉树问题了，不管是在选择题中还是在 写代码的题中，都会碰到。首先，要人脑会做，而且要有方法做，不是试出来的。主要 的思想是递归。比如前序遍历为1, 2, 4, 7, 3, 5, 6, 8，中序遍历为4, 7, 2, 1, 5, 3, 8, 6，则1肯定为根节点，然后从中序遍历中找到1,则1的左边的数字为左 子树，右边的为右子树。然...