二叉树
2022-06-24 本文已影响0人
Eden0503
[TOC]
二叉树的遍历方式
144. 二叉树的前序遍历【简单】
// https://leetcode.cn/problems/binary-tree-preorder-traversal/solution/dai-ma-sui-xiang-lu-chi-tou-qian-zhong-hou-xu-de-d/
// 前序遍历是根左右，每次先处理的是中间节点，那么先将跟节点放入栈中，然后将右孩子加入栈，再加入左孩子。
//为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。
func preorderTraversal(root *TreeNode) []int {
ans := make([]int, 0)
stack := []*TreeNode{root}
for len(stack) != 0 {
node := stack[len(stack)-1]
fmt.Println(node)
if node == nil {
stack = stack[:len(stack)-1]
continue
}
ans = append(ans, node.Val)
stack = stack[:len(stack)-1] // 栈顶元素出来
stack = append(stack, node.Right) // 先压栈右节点，再压左节点
stack = append(stack, node.Left)
}
return ans
}
145. 二叉树的后序遍历【简单】
94. 二叉树的中序遍历【简单】
102. 二叉树的层序遍历【中等】
// ============== 解法一： BFS 迭代实现，广度优先遍历 ================
func levelOrder(root *TreeNode) (res [][]int) {
if root == nil {
return res
}
queue := []*TreeNode{root}
for len(queue) != 0 {
var curLevel []int
size := len(queue)
for i := 0; i < size; i++ {
node := queue[0]
curLevel = append(curLevel, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
queue = queue[1:]
}
res = append(res, curLevel)
}
return res
}
二叉树的属性
101. 对称二叉树【简单】
104. 二叉树的最大深度【简单】
//**************** 解法一（递归走起）********************************
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
left := maxDepth(root.Left) // 左子树的最大深度
right := maxDepth(root.Right) // 右子树的最大深度
return int(math.Max(float64(left), float64(right)) + 1) // 深度加上根节点
}
//**************** 解法二（迭代法走起）********************************
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
queue := []*TreeNode{root} // 辅助队列,根节点入队
depth := 0 // 初始化深度为0
for len(queue) > 0 { // 当队列不为空时，循环以下操作
size := len(queue) //当前队列中元素个数size作为限定:当前层级中节点数量
for i := 0; i < size; i++ { // 遍历当前层级中的节点
s := queue[0] // 获取队首元素
if s.Left != nil { // 如果左子树不为空，左子树入队
queue = append(queue, s.Left)
}
if s.Right != nil { // 如果右子树不为空，右子树入队
queue = append(queue, s.Right)
}
queue = queue[1:] // 队首元素出队
}
depth++ // for循环结束后这一层级节点已经访问结束，深度加+1
}
return depth
}
111. 二叉树的最小深度【简单】
// ============== 解法一： BFS 迭代实现，广度优先遍历 ================
// https://www.cnblogs.com/Lusai/p/15709094.html
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
var queue []*TreeNode // 查找队列
queue = append(queue, root) // 将起点加入队列
depth := 1 // root 本身就是一层，depth初始化为1
for len(queue) != 0 {
size := len(queue)
// 将当前队列中的所有结点向四周扩散
for i := 0; i < size; i++ {
cur := queue[0]
// 判断是否到终点
if cur.Left == nil && cur.Right == nil {
return depth
}
// 将 cur的相邻节点加入队列
if cur.Left != nil {
queue = append(queue, cur.Left)
}
if cur.Right != nil {
queue = append(queue, cur.Right)
}
// 去掉当前节点
queue = queue[1:]
}
// 这里增加步数
depth++
}
return depth
}
// ============== 解法二： DFS ================
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
if root.Left != nil && root.Right == nil {
return 1 + minDepth(root.Left)
}
if root.Right != nil && root.Left == nil {
return 1 + minDepth(root.Right)
}
return 1 + Min(minDepth(root.Left), minDepth(root.Right))
}
