专栏首页学习日记Golang Leetcode 230. Kth Smallest Element in a BST.go

Golang Leetcode 230. Kth Smallest Element in a BST.go

版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89043444

思路

先计算左子树中节点的个数 如果左子树节点个数大于k-1,那么答案在左子树中 如果个数小于k-1,就在右子树中 如果刚好相等,就直接返回root节点的值

code

func kthSmallest(root *TreeNode, k int) int {
	left := countLeaf(root.Left)
	if left == k-1 {
		return root.Val
	} else if left > k-1 {
		return kthSmallest(root.Left, k)
	} else {
		return kthSmallest(root.Right, k-left-1)
	}
}

func countLeaf(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return countLeaf(root.Left) + countLeaf(root.Right) + 1
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Golang Leetcode 235. Lowest Common Ancestor of a Binary Search Tree.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89043473

    anakinsun
  • Golang Leetcode 965. Univalued Binary Tree.go

    更多内容请移步我的repo:https://github.com/anakin/golang-leetcode

    anakinsun
  • Golang Leetcode 450. Delete Node in a BST.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/89175007

    anakinsun
  • 二叉树高频题

    Given a binary tree, return the preorder traversal of its nodes' values.

    用户5934629
  • BST & AVL 二分搜索树 & 平衡二叉树的实现原理

    本文完整的实现了基本的BST,由于注重的是逻辑和原理的实现,所以没有采用泛型。注意方法的访问修饰符。

    大学里的混子
  • 如何使用CP / SCP / RSYNC在Linux中排除特定目录?

    对于任何系统管理员或一般Linux操作系统用户而言,在服务器之间执行文件复制操作都是一项常见任务。在将文件从一个系统复制到另一个系统时,由于某些特定原因,我们可...

    用户6543014
  • 无法从/var/lib/rpm打开软件包数据库

    薛定喵君
  • 【LeetCode】一文详解二叉树的三大遍历:前序、中序和后序(python和C++实现)

    深度学习技术前沿公众号博主
  • 【leetcode刷题】T112-验证二叉搜索树

    节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。

    木又AI帮
  • 天天算法 LeetCode-938-二叉搜索树的范围和

    https://leetcode-cn.com/problems/range-sum-of-bst/

    灵魂画师牧码

扫码关注云+社区

领取腾讯云代金券