二叉树遍历算法非递归实现

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

利用栈结构

前序核心思想为：

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/