【代码随想录】算法训练计划21、22

day 21

1、530. 二叉搜索树的最小绝对差

题目：
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。

思路：

• 利用了二叉搜索树的中序遍历特性
• 用了双指针，不用也可以

func getMinimumDifference(root *TreeNode) int {
    // 好简单，但是还是看了两眼题解，因为恐惧，下次要尝试脱离看题解了，代码一刷，中序遍历
    var pre *TreeNode
    min := math.MaxInt64
    var travel func(node *TreeNode) 
    travel = func(node *TreeNode) {
        if node == nil {
            return
        }
        travel(node.Left)
        if pre != nil && node.Val - pre.Val < min {
            min = node.Val - pre.Val
        }
        pre = node
        travel(node.Right)
    }
    travel(root)
    return min
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2、501. 二叉搜索树中的众数

题目：
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。

思路：

• 我第一次是自己写的，用的笨方法，遍历了两边map
• 可以看看计数法，也很简单，但是不需要额外空间了，卡哥的文档有写

func findMode(root *TreeNode) []int {
    // 放进map
    map1 := make(map[int]int, 0)
    zs := []int{}
    var travel func(node *TreeNode) 
    travel = func(node *TreeNode) {
        if node == nil {
            return
        }
        travel(node.Left)
        map1[node.Val]++
        travel(node.Right)
    } 
    travel(root)
    a := 0
    for _,v := range map1 {
        if v > a {
            a = v
        }
    }
    for k,v := range map1 {
        if v == a {
            zs = append(zs, k)
        }
    }
    return zs
}
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

3、236. 二叉树的最近公共祖先

题目：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思路：

• 代码一刷，后序遍历
• 后序遍历很像回溯，注意节点

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    // 代码一刷，后序遍历
    if root == nil {
        return root
    }
    if root == p || root == q {
        return root
    }
    left := lowestCommonAncestor(root.Left, p, q)
    right  := lowestCommonAncestor(root.Right, p, q)
    if left != nil && right != nil {
        return root
    }
    if left != nil {
        return left
    }
    if right != nil {
        return right
    }
    return nil
}

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

day 22

1、235. 二叉搜索树的最近公共祖先

题目：
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

思路：

• 利用二叉搜索树特点，注意最后是 <= 0

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	//代码一刷
    if root == nil {
        return nil
    }
    for {
        if root.Val > q.Val && root.Val > p.Val {
            root = root.Left
        }
        if root.Val < q.Val && root.Val < p.Val {
            root = root.Right
        }
        if (root.Val - p.Val) * (root.Val - q.Val) <= 0 {
            return root
        }
    }
    return root
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2、701. 二叉搜索树中的插入操作

题目：
给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

思路：

• 怎么我的写法就比卡尔的长了这么多代码

func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{Val:val}
    }
    travel(root,val)
    return root
}
func travel(node *TreeNode, val int) {
    if node == nil {
        return
    }
    if node.Val > val {
        if node.Left != nil {
            travel(node.Left, val)
        } else {
            node.Left = &TreeNode{Val:val}
            return
        }
    }
    if node.Val < val {
        if node.Right != nil {
            travel(node.Right, val)
        } else {
            node.Right = &TreeNode{Val:val}
            return
        }
    }
    return
}
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

3、450. 删除二叉搜索树中的节点

题目：
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点；
如果找到了，删除它。

思路：

• 同样的，利用二叉树特性

func deleteNode(root *TreeNode, key int) *TreeNode {
    // 看卡哥视频写的代码可以，看不懂文档的代码
    if root == nil {
        return nil
    }
    if key == root.Val {
        if root.Left == nil && root.Right == nil {
            return nil
        }
        if root.Left != nil && root.Right == nil {
            return root.Left
        }
        if root.Right != nil && root.Left == nil {
            return root.Right
        }
        // 左右都不为空
        cur := root.Right
        for cur.Left != nil {
            cur = cur.Left
        }
        cur.Left = root.Left
        return root.Right
    }
    if key > root.Val {
        root.Right =  deleteNode(root.Right,key)
       
    }
    if key < root.Val {
        root.Left = deleteNode(root.Left,key)
    }
    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
24
25
26
27
28
29
30
31
32