[数据结构与算法]golang数据结构篇之二叉树

二叉树遍历

前序遍历：先访问根节点，再前序遍历左子树，再前序遍历右子树
中序遍历：先中序遍历左子树，再访问根节点，再中序遍历右子树
后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点

• 以根访问顺序决定是什么遍历
• 左子树都是优先右子树

递归遍历

前中后序递归遍历换换位置即可

func preorderTraversal(root *TreeNode) {
	if root == nil {
		return
	}
	// 先访问根再访问左右
	fmt.Println(root.Val)
	preorderTraversal(root.Left)
	preorderTraversal(root.Right)
}

前序非递归

func preorderTraversal(root *TreeNode) []int {
	// 非递归
	if root == nil{
		return nil
	}
	result:=make([]int,0)
	stack:=make([]*TreeNode,0)

	for root!=nil || len(stack)!=0{
		for root !=nil{
			// 前序遍历，所以先保存结果
			result=append(result,root.Val)
			stack=append(stack,root)
			root=root.Left
		}
		// pop
		node:=stack[len(stack)-1]
		stack=stack[:len(stack)-1]
		root=node.Right
	}
	return result
}

中序非递归

// 思路：通过stack 保存已经访问的元素，用于原路返回
func inorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)
    if root == nil {
        return result
    }
    stack := make([]*TreeNode, 0)
    for len(stack) > 0 || root != nil {
        for root != nil {
            stack = append(stack, root)
            root = root.Left // 一直向左
        }
        // 弹出
        val := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result = append(result, val.Val)
        root = val.Right
    }
    return result
}

后续非递归

核心就是：根节点必须在右节点弹出之后，再弹出

func postorderTraversal(root *TreeNode) []int {
    // 通过lastVisit标识右子节点是否已经弹出
    if root == nil {
        return nil
    }
    result := make([]int, 0)
    stack := make([]*TreeNode, 0)
    var lastVisit *TreeNode
    for root != nil || len(stack) != 0 {
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }
        // 这里先看看，先不弹出
        node:= stack[len(stack)-1]
        // 根节点必须在右节点弹出之后，再弹出
        if node.Right == nil || node.Right == lastVisit {
            stack = stack[:len(stack)-1] // pop
            result = append(result, node.Val)
            // 标记当前这个节点已经弹出过
            lastVisit = node
        } else {
            root = node.Right
        }
    }
    return result
}

DFS 深搜-从上到下

func preorderTraversal(root *TreeNode) []int {
	result := make([]int, 0)
	dfs(root, &result)
	return result
}

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

DFS 深搜-从下向上（分治法）

func preorderTraversal(root *TreeNode) []int {
	result := divideAndConquer(root)
	return result
}
func divideAndConquer(root *TreeNode) []int {
	result := make([]int, 0)
	// 返回条件(null & leaf)
	if root == nil {
		return result
	}
	// 分治(Divide)
	left := divideAndConquer(root.Left)
	right := divideAndConquer(root.Right)
	// 合并结果(Conquer)
	result = append(result, root.Val)
	result = append(result, left...)
	result = append(result, right...)
	return result
}

DFS 深度搜索（从上到下） 和分治法区别：前者一般将最终结果通过指针参数传入，后者一般递归返回结果最后合并

BFS 层次遍历

func levelOrder(root *TreeNode) [][]int {
    // 通过上一层的长度确定下一层的元素
    result := make([][]int, 0)
    if root == nil {
        return result
    }
    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    for len(queue) > 0 {
        list := make([]int, 0)
        // 为什么要取length？
        // 记录当前层有多少元素（遍历当前层，再添加下一层）
        l := len(queue)
        for i := 0; i < l; i++ {
            // 出队列
            level := queue[0]
            queue = queue[1:]
            list = append(list, level.Val)
            if level.Left != nil {
                queue = append(queue, level.Left)
            }
            if level.Right != nil {
                queue = append(queue, level.Right)
            }
        }
        result = append(result, list)
    }
    return result
}