树

# 树的递归

# 二叉树的最大深度

104. 二叉树的最大深度 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

终于没看题解做对了一个，太难了，不过这题目比较简单，所以没啥炫耀的，害

func maxDepth(root *TreeNode) int {
   if root == nil {
      return 0
   }
   // 分别计算左右子树的高度
   l:=maxDepth(root.Left)+1
   r:=maxDepth(root.Right)+1
   if l > r {
      return l
   } else {
      return r
   }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 层次遍历

一般都是使用广度优先搜索进行层次遍历

# 二叉树的层平均值

637. 二叉树的层平均值 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题目主要是考二叉树的层次遍历，我们可以使用队列来进行求解

type TreeNode struct {
   Val int
   Left *TreeNode
   Right *TreeNode
}
type Queue struct {
   data []*TreeNode
}
func (q *Queue)Push(k *TreeNode)  {
   q.data = append(q.data, k)
}
func (q *Queue)Pop() (i *TreeNode) {
   i = q.data[0]
   q.data = q.data[1:]
   return
}
func (q *Queue)Front() (i *TreeNode) {
   return q.data[0]
}
func (q *Queue)Empty() bool {
   return len(q.data)==0
}
func averageOfLevels(root *TreeNode) []float64 {
   var ans []float64
   // 节点为空时，我们直接返回结果
   if root== nil {
      return ans
   }
   // 初始化队列
   q:=Queue{}
   // 先把当前节点入队
   q.Push(root)
   // 当q为空时退出
   for !q.Empty() {
      // 当前队列的大小
      count:= len(q.data)
      // 队列和
      sum:=0
      for i := 0; i < count; i++ {
         // q出队
         node:=q.Pop()
         // 然后计算和
         sum+=node.Val
         // 下面我们就把下一层的节点推入队列(包括左右节点)
         if node.Left!=nil {
            q.Push(node.Left)
         }
         if node.Right!=nil {
            q.Push(node.Right)
         }
      }
      // 计算当前层的平均值
      ans = append(ans, float64(sum)/float64(count))
   }
   return ans
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

# 前中后序遍历

# 从前序与中序遍历序列构造二叉树

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题emm，先跳过，后面在详细研究一下思路

func buildTree(preorder []int, inorder []int) *TreeNode {
   if len(preorder) == 0 {
      return nil
   }
   hash:=make(map[int]int)
   for i := 0; i < len(preorder); i++ {
      hash[inorder[i]] = i
   }
   return buildHelp(hash,preorder,0,len(preorder)-1,0)
}

func buildHelp(hash map[int]int,preorder []int,s0 int,e0 int,s1 int) *TreeNode {
   if s0 > e0 {
      return nil
   }
   mid:=preorder[s1]
   index:=hash[mid]
   leftLen :=index-s0-1
   node:=TreeNode{Val: mid}
   node.Left = buildHelp(hash,preorder,s0,index-1,s1+1)
   node.Right = buildHelp(hash,preorder,index+1,e0,s1+2+leftLen)
   return &node
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 二叉树展开为链表

114. 二叉树展开为链表 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 二叉查找树

二叉查找树（Binary Search Tree, BST）是一种特殊的二叉树：对于每个父节点，其左子节点的值小于等于父结点的值，其右子节点的值大于等于父结点的值。因此对于一个二叉查找树，我们可以在 O(n log n) 的时间内查找一个值是否存在：从根节点开始，若当前节点的值大于查找值则向左下走，若当前节点的值小于查找值则向右下走。同时因为二叉查找树是有序的，对其中序遍历的结果即为排好序的数组。

# 恢复二叉查找树

99. 恢复二叉搜索树 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 修剪二叉搜索树

669. 修剪二叉搜索树 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 字典树

用于判断字符串是否存在或者具有某种字符串前缀

# 实现前缀树

208. 实现 Trie (前缀树) - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

编辑

上次更新: 2021/03/30, 08:39:06

← 链表图→

树