144.二叉树的前序遍历

遍历方式

如果对每一个节点进行编号，你会用什么方式去遍历每个节点呢？

如果你按照 根节点 -> 左孩子 -> 右孩子 的方式遍历，即「先序遍历」，每次先遍历根节点，遍历结果为 1 2 4 5 3 6 7；
同理，如果你按照 左孩子 -> 根节点 -> 右孩子 的方式遍历，即「中序序遍历」，遍历结果为 4 2 5 1 6 3 7；
如果你按照 左孩子 -> 右孩子 -> 根节点 的方式遍历，即「后序序遍历」，遍历结果为 4 5 2 6 7 3 1；
最后，层次遍历就是按照每一层从左向右的方式进行遍历，遍历结果为 1 2 3 4 5 6 7。

方法一：颜色标记法

//3,颜色标记法,通法=变化顺序即可，反序变颜色，人工维护一个栈，==迭代的思路
func inorderTraversal(root *TreeNode) []int {
    type node struct {      //1,定义颜色，0表示白色，为遍历，1表示灰色，遍历过
        Color int
        Node *TreeNode
        }
    stack := make([]node, 0)    //2,初始化栈，手动维护
    rootNode := node{0, root}    //初始化根节点
    stack = append(stack, rootNode) //3,把根节点依次放入栈中，第一次入栈
    res := make([]int,0)
    for len(stack) >0 {             //4,入栈的模拟，父节点依次入栈
        n := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if n.Node == nil {          //5,入栈模拟，结束条件，没有父节点时
            continue
        }
        if n.Color == 0 {           //6.入栈模拟,核心，对白色的，未标记的进行遍历，入栈右中左,反序出栈
            stack = append(stack, node{0, n.Node.Right})
            //stack = append(stack, node{1, n.Node}) //访问后，白色变灰色
            stack = append(stack, node{0, n.Node.Left})
            stack = append(stack, node{1, n.Node}) //变一下这行就行
        } else {
            res = append(res , n.Node.Val)  
            //7,颜色为灰色，因为中序中根节点会被访问2次，输出第二次访问结果
        }
    }
    return res
}

func preorderTraversal(root *TreeNode) []int {
    //存储结果
    var res []int
    if root == nil {
        return res
    }

    //通过栈控制遍历顺序
    stack := []*TreeNode{root}
    //用map标记某个节点是否 遍历过
    marks := make(map[*TreeNode]bool)

    var node *TreeNode
    for len(stack) != 0 {

        //pop最后一个节点
        node = stack[len(stack) - 1]        //取栈顶元素
        stack = stack[:len(stack) - 1]        //出栈，两步删除栈顶 


        //如果节点已经遍历过，则打印
        _, ok := marks[node]
        if ok {
            res = append(res, node.Val)
        } else {
            //核心倒序出栈，否则入栈该节点和右子树，左子树，并标记当前节点已经遍历过(下次不再处理，可直接打印)

            //TODO-3 更改下行代码的位置 可以转换 前序，中序，后序遍历(当前为后序遍历)
            //stack = append(stack, node)

            if node.Right != nil {
                stack = append(stack, node.Right)
            }

            //TODO-2 上述代码放到这里即 中序遍历
            if node.Left != nil {
                stack = append(stack, node.Left)
            }

            //TODO-1 上述代码放到这里即 前序遍历
            stack = append(stack, node)        //前

            marks[node] = true
        }
    }
    return res
}

方法二：递归法

//1，递归
func preorderTraversal(root *TreeNode) []int {
    res := []int{}      //暂存一个数组 来存二叉树的值
    preorder(root, &res) //递归函数，父节点，遍历值
    return res          //返回结果数组
}

func preorder(root *TreeNode, res *[]int) {
    if root == nil {        //终止条件，根节点为空
        return
    }

    *res = append(*res,root.Val) //换这行位置，中前后前序遍历
    preorder(root.Left,res)  //中序遍历，前中后子树，核心三句
    //*res = append(*res,root.Val)
    preorder(root.Right,res)    //用递归函数的方式，取右节点值
}

方法三：迭代法

//2，迭代
func preorderTraversal(root *TreeNode) []int {
    stack := []*TreeNode{}
    res := []int{}

    for root != nil || len(stack) > 0 {
        for root != nil {
            res = append(res, root.Val) //前序
            stack = append(stack, root)
            root = root.Left
        }

        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        //res = append(res, root.Val)   //变化的句子
        root = root.Right
    }
    return res
}

4. 总结

总结一下，在二叉树的前序、中序、后序遍历中，递归实现的伪代码为：
参考，链接

迭代实现的伪代码为：

掌握了以上基本的遍历方式，对待更多的进阶题目就游刃有余了。