NC45 实现二叉树先序，中序和后序遍历

题目描述

分别按照二叉树先序，中序和后序打印所有的节点。
示例1
输入：
{1,2,3}
返回值：
[[1,2,3],[2,1,3],[2,3,1]]

解题思路

很简单。但是这个题是用golang做的，golang的list作为参数传递时有个坑。

使用数组元素(array[x])或者数组(array)，或者结构体作为函数参数时，其使用方法和普通变量相同，即是值传递。
但是传递slice的时候不一样。切片本身并不是动态数组或者数组指针。它内部实现的数据结构通过指针引用底层数组，设定相关属性将数据读写限定在制定的区域内。切片本身是一个只读对象，其工作机制类似数组指针的一种封装。
type slice struct {
    array unsafe.Pointer
    len int
    cap int
}
如果把slice作为函数参数，并在函数内部修改过了的话，只会修改array指针，但是len和cap不会被修改。因此建议函数参数使用指向slice的指针。

解题代码

func pre_order(root *TreeNode, pre_list *[]int) {
    if root == nil {
        return
    }
    *pre_list = append(*pre_list, root.Val)
    pre_order(root.Left, pre_list)
    pre_order(root.Right, pre_list)
}

func in_order(root *TreeNode, in_list *[]int) {
    if root == nil {
        return
    }
    in_order(root.Left, in_list)
    *in_list = append(*in_list, root.Val)
    in_order(root.Right, in_list)
}

func post_order(root *TreeNode, post_list *[]int) {
    if root == nil {
        return
    }
    post_order(root.Left, post_list)
    post_order(root.Right, post_list)
    *post_list = append(*post_list, root.Val)
}

func threeOrders(root *TreeNode) [][]int {
    var result [][]int
    var pre_list, in_list, post_list []int
    pre_order(root, &pre_list)
    in_order(root, &in_list)
    post_order(root, &post_list)
    result = append(result, pre_list, in_list, post_list)
    return result
}

执行结果

运行时间：4ms
超过58.49% 用Go提交的代码
占用内存：1480KB
超过15.12%用Go提交的代码

非递归做法

除了使用递归之外，还可以使用辅助栈遍历。无论哪种遍历，都需要严格注意以下句子的前后出现顺序：

print(node.val)
node = node.left
node = node.right

遍历的写法类似，都需要以下结构（非常重要）：

stack = []
while stack or node:
    while node:

而且编写过程中都不需要判断左右子树是否存在。

前序遍历

前序遍历的编写方式如下所示：

def Traverse(root):
    if not root:
        return None
    stack = []
    node = root
    # 注意这个是or，因为初始的stack里面是空的，而遍历到空节点也是None，因此可以一个while一举两得
    while stack or node:
        while node:
            stack.append(node)
            print(node.val)
            node = node.left
        node = stack.pop().right

中序遍历

中序遍历的编写方式如下所示：

def inorderTraversal(root: TreeNode):
    stack =[]
    node = root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        print(node.val)
        node = node.right

后序遍历

后序遍历就是先把修改过的前序遍历（中左右改为中右左）放在栈里，再把栈里面都pop出来，就一次性得到后序遍历结果（左右中）

def postorderTraversal(self , root: TreeNode):
    res = []
    stack= []
    node = root
    while stack or node:
        while node:
            stack.append(node)
            res.append(node.val)
            node = node.right
        node = stack.pop().left
    return res[::-1]