二叉树的DFS-BFS遍历，分而治之…代码记录

完整代码

• 新建文件
• 复制粘贴
• 运行代码

效果截图

测试数据

运行结果

代码

package main

import (
	"log"
)

type Node struct {
	Val   int
	Left  *Node
	Right *Node
}

// 测试数据
// 	3
// / \
// 9  20
//  /  \
// 15   7
func main() {
	tree := Node{}
	tree.Val = 3
	tree.Left = &Node{
		Val: 9,
	}
	tree.Right = &Node{
		Val: 20,
		Left: &Node{
			Val: 15,
		},
		Right: &Node{
			Val: 7,
		},
	}
	log.Printf("%-10s\t%v", "深度优先(先序)", Dfs(&tree))
	log.Printf("%-10s\t%v", "深度优先(先序)-分治", DfsDivide(&tree))
	log.Printf("%-10s\t%v", "广度优先-层次", Bfs(&tree))
}

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

// 深度优先
func Dfs(root *Node) []int {
	ret := make([]int, 0, 4)
	dfs(root, &ret)
	return ret
}
func dfs(root *Node, ret *[]int) {
	if root == nil {
		return
	}
	*ret = append(*ret, root.Val)
	dfs(root.Left, ret)
	dfs(root.Right, ret)
}

// 深度优先-分治
func DfsDivide(root *Node) []int {
	ret := make([]int, 0, 4)
	if root == nil {
		return ret
	}
	left := DfsDivide(root.Left)
	right := DfsDivide(root.Right)
	ret = append(ret, root.Val)
	ret = append(ret, left...)
	ret = append(ret, right...)
	return ret
}

// 广度优先
func Bfs(root *Node) [][]int {
	ret := make([][]int, 0, 4)
	queue := make([]*Node, 0, 4)
	queue = append(queue, root)
	// 队列里面有节点就一直计算
	for len(queue) > 0 {
		// 队列目前长度-当前树层有多少个节点
		ln := len(queue)
		item := make([]int, 0, 4)
		for i := 0; i < ln; i++ {
			// 出队
			curr := queue[0]
			queue = queue[1:]
			// 以此加入左右子节点
			if curr.Left != nil {
				queue = append(queue, curr.Left)
			}
			if curr.Right != nil {
				queue = append(queue, curr.Right)
			}
			item = append(item, curr.Val)
		}
		ret = append(ret, item)
	}
	return ret
}