代码随想录算法训练营第十八天 | 530、501、236

算法
, , ,

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

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
package main

import "math"

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func getMinimumDifference(root *TreeNode) int {
    var prev *int
    minDiff := math.MaxInt32

    var inorder func(node *TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        inorder(node.Left)
        if prev != nil {
            diff := node.Val - *prev
            if diff < minDiff {
                minDiff = diff
            }
        }
        temp := node.Val
        prev = &temp
        inorder(node.Right)
    }

    inorder(root)
    return minDiff
}

501. 二叉搜索树中的众数

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
package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findMode(root *TreeNode) []int {
    var modes []int
    var prev *TreeNode
    maxCount, currentCount := 0, 0

    var inorder func(node *TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        inorder(node.Left)

        if prev != nil && prev.Val == node.Val {
            currentCount++
        } else {
            currentCount = 1
        }

        if currentCount > maxCount {
            maxCount = currentCount
            modes = []int{node.Val}
        } else if currentCount == maxCount {
            modes = append(modes, node.Val)
        }

        prev = node
        inorder(node.Right)
    }

    inorder(root)
    return modes
}

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

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
package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
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 && right != nil {
        return root
    }
    if left != nil {
        return left
    }
    return right
}