树
树是一个大类 包括二叉树，二叉搜索树，AVL树，红黑树，N叉树等等。树的算法题大多都可以使用递归进行解决。
二叉树
二叉树是指的是节点有小于等于两个出度的树，二叉树算是最基本的树，很多算法题目也是在二叉树的基础上出题。
二叉树的遍历
二叉树的主要有四种遍历方式，前序遍历，中序遍历，后序遍历以及层次遍历。前中后序遍历指的都是根节点在遍历过程中的顺序位置。
前序遍历
前序遍历的顺序就是中前后，先访问根节点，之后再递归访问左子树最后是右子树。
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
|
// 递归实现
func preorderRecursive(root *TreeNode, res *[]int) {
//递归方式
if root == nil {
return
}
*res = append(*res, root.Val)
preorderRecursive(root.Left, res)
preorderRecursive(root.Right, res)
}
// 使用栈来代替系统栈
func preorder(root *TreeNode) []int {
//使用栈来代替系统栈
//刚好和后续相反，只不过在加入栈的时候就进行了访问
stack := make([]*TreeNode, 0)
res := make([]int, 0)
for len(stack) != 0 || root != nil {
//遍历左子树 包括根节点
for root != nil {
stack = append(stack, root)
res = append(res, root.Val)
root = root.Left
}
//弹出
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
root = root.Right
}
return res
}
|
中序遍历
中序遍历则是先访问左边节点之后是根节点，最后才是右子树。
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
|
// 递归
func inorderRecursive(root *TreeNode, res *[]int) {
//递归方式
if root == nil {
return
}
preorderRecursive(root.Left, res)
*res = append(*res, root.Val)
preorderRecursive(root.Right, res)
}
// 使用栈
func inorderTraversal(root *TreeNode) []int {
res := make([]int, 0)
stack := make([]*TreeNode, 0)
//由于右子树可能为空
for len(stack) != 0 || root != nil {
//遍历左子树
for root != nil {
stack = append(stack, root)
root = root.Left
}
//取出栈顶节点
root = stack[len(stack)-1]
res = append(res, root.Val)
stack = stack[:len(stack)-1]
root = root.Right
}
return res
}
|
后序遍历
后序遍历则是根节点最后访问，访问左子树之后紧跟着访问右子树。
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
|
// 递归访问
func postorderRecursive(root *TreeNode, res *[]int) {
//递归方式
if root == nil {
return
}
preorderRecursive(root.Left, res)
preorderRecursive(root.Right, res)
*res = append(*res, root.Val)
}
// 使用栈
func postorderTraversal(root *TreeNode) []int {
stack := make([]*TreeNode, 0)
res := make([]int, 0)
var prev *TreeNode
for len(stack) != 0 || root != nil {
for root != nil {
stack = append(stack, root)
root = root.Left
}
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
if root.Right == nil || root.Right == prev {
res = append(res, root.Val)
prev = root
root = nil
} else {
stack = append(stack, root)
root = root.Right
}
}
return res
}
|
层次遍历
层次遍历则是使用队列或者是叫做广度优先遍历，一层一层的访问所有的节点，一般层次遍历类型的题目较为简单。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
func levelOrder(root *TreeNode) [][]int {
//层次遍历
queue := make([]*TreeNode, 0)
res := make([][]int, 0)
queue = append(queue, root)
for len(queue) != 0 && root != nil {
temp := make([]int, 0)
size := len(queue)
for i := 0; i < size; i++ {
temp = append(temp, queue[i].Val)
if queue[i].Left != nil {
queue = append(queue, queue[i].Left)
}
if queue[i].Right != nil {
queue = append(queue, queue[i].Right)
}
}
queue = queue[size:]
res = append(res, temp)
}
return res
}
|
这道题如果搞清楚什么情况才会赢是很简单的。因为最后比较的是着色的数量。所以二号玩家着色的位置只有三个位置：
- 一号玩家着色节点的左子树，想赢的话肯定要选择左孩子
- 一号玩家着色节点的右子树，右孩子
- 除了上述位置的其他位置，直接一号玩家着色节点的父节点
所以我们只需要统计一下这三个位置的节点数即可。然后只要该位置节点数大于另外两个位置节点数就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
func btreeGameWinningMove(root *TreeNode, n int, x int) bool {
if nil == root {
return false
}
xLeftSum, xRightSum := 0, 0 //x节点的左子树和右子树节点个数
sum := execute(root, x, &xLeftSum, &xRightSum)
other := sum - xLeftSum - xRightSum - 1 //其余节点个数
return other > xLeftSum + xRightSum || xLeftSum > other + xRightSum || xRightSum > other + xLeftSum
}
func execute(root *TreeNode, x int, xLeftSum, xRightSum *int) (int) {
if nil == root {
return 0
}
left := execute(root.Left, x, xLeftSum, xRightSum)
right := execute(root.Right, x, xLeftSum, xRightSum)
if root.Val == x {
*xLeftSum = left
*xRightSum = right
}
return 1 + left + right
}
|
二叉树对称、镜像类型的题目
给定一个二叉树，检查它是否是镜像对称的。
对称二叉树说的是整个树的对称，所以需要判断两种情况
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
|
func isSymmetric(root *TreeNode) bool {
//对称是整个树的对称
if root == nil {
return true
}
return Symmetric(root.Left, root.Right)
}
func Symmetric(left, right *TreeNode) bool {
if left == nil && right == nil {
return true
}
if left == nil || right {
return false
}
if left.Val != right.Val {
return false
}
return Symmetric(left.Left,right.Right) && Symmetric(left.Right, right.Left)
}
// 迭代的方式
// 迭代的方式就是通过将需要比较的节点暂时存储到队列中，之后再从队列中取出进行比较。
func isSymmetric(root *TreeNode) bool {
u, v := root, root
q := []*TreeNode{}
q = append(q, u)
q = append(q, v)
for len(q) > 0 {
u, v = q[0], q[1]
q = q[2:]
// 判断的部分没有进行改变
if u == nil && v == nil {
continue
}
if u == nil || v == nil {
return false
}
if u.Val != v.Val {
return false
}
q = append(q, u.Left)
q = append(q, v.Right)
q = append(q, u.Right)
q = append(q, v.Left)
}
return true
}
|
翻转二叉树类似于镜像二叉树，翻转是从最后的叶子节点开始进行反转.所以是先进行递归后续进行
1
2
3
4
5
6
7
8
9
10
|
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
left := invertTree(root.Left)
right := invertTree(root.Right)
root.Left = right
root.Right = left
return root
}
|
与二叉树的深度相关的题目
一般情况下与二叉树深度相关的题目也不会太难。
判断二叉树的最大深度即判断每个根节点到叶子节点的最长路径上的节点数，即遇到nil节点返回0，其他加1.
1
2
3
4
5
6
|
func maxDepth(root *TreeNode) int {
if root==nil {
return 0
}
return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}
|
不同于二叉树的最大深度，最小深度如果使用最大深度的那种做法，则在单边树则会出现问题，更加稳健的做法应该是将问题缩小为判断左子树和右子树，并且不计算nil节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
if root.Left == nil && root.Right == nil {
return 1
}
minD := math.MaxInt32
if root.Left != nil {
minD = min(minDepth(root.Left), minD)
}
if root.Right != nil {
minD = min(minDepth(root.Right), minD)
}
return minD + 1
}
|
平衡二叉树的定义是一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。所以说可以通过判断左右子树的深度差来判断该二叉树是否为平衡二叉树。
1
2
3
4
5
6
7
8
9
10
11
|
func isBalanced(root *TreeNode) bool {
if root == nil {
return true
}
left := depth(root.Left)
right := depth(root.Right)
if abs(left-right) > 1 {
return false
}
return isBalanced(root.Left) && isBalanced(root.Right)
}
|
一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。但是这个这个最长路径所经过的节点一定位于一个节点的左右子树，除非该节点没有左右子树。所以我们只需要计算该节点左右子树的最大深度之后相加即为直径的长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
func diameterOfBinaryTree(root *TreeNode) int {
res := 0
var depth func(t *TreeNode) int
depth = func(t *TreeNode) int {
if t == nil {
return 0
}
left := depth(t.Left)
right := depth(t.Right)
res = max(res, left + right-2)
return max(left, right) + 1
}
depth(root)
return res
}
|
祖先问题
二叉树的公共祖先
公共祖先的问题有一个基本点就是自己可以算作自己的祖先，那么我们就可以按个搜索目标节点之后返回不为nil的那一只节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root ==nil || root == p || root==q {
return root
}
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
if left == nil {
return right
}
if right == nil {
return left
}
return root
}
|
二叉树路径问题
路径一般指的是根节点到叶子节点的节点顺序。而寻找路径的情况下最多使用的方式是回溯，减少重复计算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
func binaryTreePaths(root *TreeNode) []string {
res := make([]string,0)
var bk func(t *TreeNode, cur []int)
bk = func(t *TreeNode, cur []int) {
if t.Left == nil && t.Right == nil {
// 回溯截止
temp := ""
for _,v := range cur {
temp += (strconv.Itoa(v) + "->")
}
res = append(res, temp + strconv.Itoa(t.Val))
}
if t.Left != nil {
bk(t.Left, append(cur, t.Val))
}
if t.Right != nil {
bk(t.Right, append(cur, t.Val))
}
}
bk(root, make([]int,0))
return res
}
|
二叉搜索树
二叉搜索树（BST）是当前节点的值大于等于其左子树的值，小于等于其右子树的值。所以二叉搜索树中序遍历结果是有序递增的。二分查找的搜索顺序就是一颗二分搜索树。
相当于是对一个有序数组进行二分查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
func searchBST(root *TreeNode, val int) *TreeNode {
if root == nil {
return nil
}
for root != nil {
temp := root.Val
if temp == val {
return root
} else if temp > val {
root = root.Left
} else {
root = root.Right
}
}
return nil
}
|
从有序数组中创建高度最小树，则使用二分搜索创建即可，根节点的左右子树高度应该尽可能的相同。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
func sortedArrayToBST(nums []int) *TreeNode {
// 高度最小 则应该是创建为 二分搜索树
var build func(l,h int) *TreeNode
build = func(l,h int) *TreeNode {
if l > h {
return nil
}
mid := l + (h-l) / 2
root := &TreeNode{Val: nums[mid]}
root.Left = build(l, mid-1)
root.Right = build(mid+1, h)
return root
}
return build(0,len(nums)-1)
}
|
二叉搜索树的性质就是左子树都比根节点小，右子树都比根节点大。我们可以知道随意给一个序列生成二叉搜索树的方式，那么我们可以随机选择一个点，然后一次作为分割，在两边生成不同的二叉搜索树。然后在整合到根节点上。注意：两边的二叉搜索树可能有多个，并不是必定一个
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
|
func generateTrees(n int) []*TreeNode {
if n == 0 {
return nil
}
return build(1, n)
}
func build(l, h int) []*TreeNode {
if l > h {
return []*TreeNode{nil}
}
allTrees := []*TreeNode{}
for i:=l;i<=h;i++ {
// 在这个区间中枚举所有可以为根节点
leftTrees := build(l, i-1)
rightTrees := build(i+1, h)
for _,left := range leftTrees {
for _, right := range rightTrees {
root := &TreeNode{Val: i}
root.Left = left
root.Right = right
allTrees = append(allTrees, root)
}
}
}
return allTrees
}
|
如果不需要具体的二叉搜索树只需要能够生成的数量，则可以使用动态规划。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
func numTrees(n int) int {
// 一个节点只能够构成一个 二叉搜索树
// 两个节点可以构成两个二叉搜索树
// 三个节点的话 就是分别枚举所有可能的根节点，然后左子树的个数乘以右子树的个数
// 如果为空个数设置为1 即dp[0] = 1
// 状态转移方程 dp[i] = dp[i-1] * dp[n-i]
dp := make([]int, n+1)
dp[0] = 1
dp[1] = 1
for i:=2;i<=n;i++ {
for j:=1;j<=i;j++ {
dp[i] += dp[j-1] * dp[i-j]
}
}
return dp[n]
}
|