寒假的时候百度实习一面被问到了这个，没做出来，补习一下

利用栈结构

前序核心思想为：

1. 每拿到一个 节点 就把它保存在 栈 中
2. 继续对这个节点的 左子树 重复 过程1，直到左子树为 空
3. 因为保存在 栈 中的节点都遍历了 左子树 但是没有遍历 右子树，所以对栈中节点 出栈 并对它的 右子树 重复 过程1，2
4. 直到遍历完所有节点
   前序中序后序都通用的模板为（以前序遍历为例）

 def preorderTraversal(root: TreeNode): List[Int] = {    // 用一个栈来保存中间结果    val stack = new mutable.Stack[TreeNode]()    val result = new mutable.ListBuffer[Int]()    var temp = root    while(temp != null || stack.nonEmpty) {      if (temp != null) {        // 每遇到一个节点，就把它加入结果集，并把该节点保存到中间结果中        result.+=(temp.value)        stack.push(temp)        // 先遍历左子树，一直走到空        temp = temp.left      } else {        // 左子树走到空，就从获取已经遍历过左子树的中间结果，将它出栈，并遍历它的右子树        val node = stack.pop()        temp = node.right      }    }作者：18211010139链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/die-dai-jie-fa-shi-jian-fu-za-du-onkong-jian-fu-za/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

中序遍历在出栈时访问结点
后序遍历将插入结果列表尾部改为头部，先查看右节点再看左节点
参考资料
https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/die-dai-jie-fa-shi-jian-fu-za-du-onkong-jian-fu-za/

原著是一个有趣的人,若有侵权,请通知删除