February 2, 2022: the closest binary search tree value II. Given a non empty two

2022-02-02： The closest binary search tree value II.

Given a binary search tree that is not empty and a target value target, Please find the closest target value in the binary search tree target Of k It's worth .

Be careful ：

Given target value target Is a floating point number ,

You can default k Value is always valid , namely k ≤ Sum up points ,

The title guarantees that there will be only one kind of... In the binary search tree k Sets of values closest to the target value .

expand ：

Suppose the binary search tree is balanced , Would you please tell me if you can make it less than O(n)（n To sum up the points ） The time complexity of solving the problem ？

Power button 272.

answer 2022-02-02：

【 Precursor node - The target 】 and 【 Precursor node - The target 】, The closer we get target, Take this node . The precursor node is taken , Left expansion ; Take the rear drive node , Right expansion .

Prepare two stacks , Quick support for finding precursors and successors .

Time complexity ： lower than O(N).

Spatial complexity ： lower than O(N).

The code to use golang To write . The code is as follows ：

package main

import "fmt"

func main() {
    root := &TreeNode{val: 4}
    root.left = &TreeNode{val: 2}
    root.right = &TreeNode{val: 5}
    root.left.left = &TreeNode{val: 1}
    root.left.right = &TreeNode{val: 3}
    ret := closestKValues(root, 3.713286, 2)
    fmt.Println(ret)
}

type TreeNode struct {
    val   int
    left  *TreeNode
    right *TreeNode
}

func NewTreeNode(val int) *TreeNode {
    ans := &TreeNode{}
    ans.val = val
    return ans
}

//  This solution comes from the answer in the discussion area , The optimal solution is easy to understand and beautiful 
func closestKValues(root *TreeNode, target float64, k int) []int {
    ret := make([]int, 0)
    // >=8, The nearest node , And we need to quickly find such a structure 
    moreTops := make([]*TreeNode, 0)
    // <=8, The nearest node , And we need to quickly find such a structure of precursor 
    lessTops := make([]*TreeNode, 0)
    getMoreTops(root, target, &moreTops)
    getLessTops(root, target, &lessTops)
    if len(moreTops) > 0 && len(lessTops) > 0 && moreTops[len(moreTops)-1].val == lessTops[len(lessTops)-1].val {
        getPredecessor(&lessTops)
    }
    for k > 0 {
        k--
        if len(moreTops) == 0 {
            ret = append(ret, getPredecessor(&lessTops))
        } else if len(lessTops) == 0 {
            ret = append(ret, getSuccessor(&moreTops))
        } else {
            diffs := abs(float64(moreTops[len(moreTops)-1].val) - target)
            diffp := abs(float64(lessTops[len(lessTops)-1].val) - target)
            if diffs < diffp {
                ret = append(ret, getSuccessor(&moreTops))
            } else {
                ret = append(ret, getPredecessor(&lessTops))
            }
        }
    }
    return ret
}

func abs(d float64) float64 {
    if d < 0 {
        return -d
    } else {
        return d
    }

}

//  stay root For the head of the tree 
//  find >=target, And closest to target The node of 
//  And in the process of searching , Just a node x Left , Just put x Put in moreTops in 
func getMoreTops(root *TreeNode, target float64, moreTops *[]*TreeNode) {
    for root != nil {
        if root.val == int(target) {
            *moreTops = append(*moreTops, root)
            break
        } else if root.val > int(target) {
            *moreTops = append(*moreTops, root)
            root = root.left
        } else {
            root = root.right
        }
    }
}

//  stay root For the head of the tree 
//  find <=target, And closest to target The node of 
//  And in the process of searching , Just a node x Go to the right , Just put x Put in lessTops in 
func getLessTops(root *TreeNode, target float64, lessTops *[]*TreeNode) {
    for root != nil {
        if root.val == int(target) {
            *lessTops = append(*lessTops, root)
            break
        } else if root.val < int(target) {
            *lessTops = append(*lessTops, root)
            root = root.right
        } else {
            root = root.left
        }
    }
}

//  return moreTops Value of the header of 
//  And adjust moreTops :  In order to quickly find the successor node of the return node in the future 
func getSuccessor(moreTops *[]*TreeNode) int {
    cur := (*moreTops)[len(*moreTops)-1]
    *moreTops = (*moreTops)[0 : len(*moreTops)-1]
    ret := cur.val
    cur = cur.right
    for cur != nil {
        *moreTops = append(*moreTops, cur)
        cur = cur.left
    }
    return ret
}

//  return lessTops Value of the header of 
//  And adjust lessTops :  In order to quickly find the precursor node of the return node in the future 
func getPredecessor(lessTops *[]*TreeNode) int {
    cur := (*lessTops)[len(*lessTops)-1]
    *lessTops = (*lessTops)[0 : len(*lessTops)-1]
    ret := cur.val
    cur = cur.left
    for cur != nil {
        *lessTops = append(*lessTops, cur)
        cur = cur.right
    }
    return ret
}

The results are as follows ：

picture

Zuo Shen java Code