golang 实现二叉搜索树中第K小的元素

ゝ一纸荒年。 2022-03-08 11:26 64阅读 0赞

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
    
    说明：
    你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
    
    示例 1:
    
    输入: root = [3,1,4,null,2], k = 1
       3
      / \
     1   4
      \
       2
    输出: 1
    示例 2:
    
    输入: root = [5,3,6,2,4,null,null,1], k = 3
           5
          / \
         3   6
        / \
       2   4
      /
     1
    输出: 3
    进阶：
    如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？
    --------------------- 
    作者：Mr_Curious_ 
    来源：CSDN 
    原文：https://blog.csdn.net/xuchonghao/article/details/80770490 
    版权声明：本文为博主原创文章，转载请附上博文链接！

golang语言使用中序遍历，使用栈

/**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    func kthSmallest(root *TreeNode, k int) int {
        //中序遍历
        if root==nil || k<=0{
            return -1
        }
        s:=NewStack()
        GetBTVal(root ,s )
        fmt.Println(s.Val)
        
        for index,v:=range s.Val{
            
            if index+1==k{
                return v
            }
            
        }
       
        
        return -1
        
    }
    
    
    
    type Stack struct{
        Val []int
        Top int
    }
    
    func NewStack()*Stack{
        return &Stack{Val:make([]int,0),Top:0}
    }
    
    func (s *Stack)Push(v int){
        s.Val=append(s.Val,v)
        
    }
    
    func (s *Stack)Pop()int{
        if s.Top==0{
            return -1
        }
        
        v:=s.Val[s.Top-1]
        s.Top--
        return v
    }
    
    func (s *Stack)IsEmpty()bool{
        if s.Top==0{
          return  true
        }
        
        return false
        
    }
    
    func GetBTVal(root *TreeNode,s *Stack){
        
        if root==nil{
            return 
        }
        
        GetBTVal(root.Left,s)
        s.Val =append(s.Val,root.Val)
       
        GetBTVal(root.Right,s) 
         
    }