Golang | Leetcode Golang题解之第230题二叉搜索树中第K小的元素

题目：

题解：

type MyBst struct {
    root    *TreeNode
    nodeNum map[*TreeNode]int // 统计以每个结点为根结点的子树的结点数，并存储在哈希表中
}

// 统计以 node 为根结点的子树的结点数
func (t *MyBst) countNodeNum(node *TreeNode) int {
    if node == nil {
        return 0
    }
    t.nodeNum[node] = 1 + t.countNodeNum(node.Left) + t.countNodeNum(node.Right)
    return t.nodeNum[node]
}

// 返回二叉搜索树中第 k 小的元素
func (t *MyBst) kthSmallest(k int) int {
    node := t.root
    for {
        leftNodeNum := t.nodeNum[node.Left]
        if leftNodeNum < k-1 {
            node = node.Right
            k -= leftNodeNum + 1
        } else if leftNodeNum == k-1 {
            return node.Val
        } else {
            node = node.Left
        }
    }
}

func kthSmallest(root *TreeNode, k int) int {
    t := &MyBst{root, map[*TreeNode]int{}}
    t.countNodeNum(root)
    return t.kthSmallest(k)
}

原文地址：https://blog.csdn.net/weixin_66442839/article/details/140367527

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！