备案控制台
开发者社区 开发与运维 文章 正文

Golang每日一练(leetDay0084) BST第K小的元素、最近公共祖先

2024-01-30 24
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： Golang每日一练(leetDay0084) BST第K小的元素、最近公共祖先

230. 二叉搜索树中第K小的元素 Kth-smallest Element In A BST

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1

输出：1


示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3

输出：3


提示：

  • 树中的节点数为 n 。
  • 1 <= k <= n <= 10^4
  • 0 <= Node.val <= 10^4

进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

代码1：BST特性：中序遍历会得到一个递增的序列，序列第k-1个元素即结果

package main
import (
  "fmt"
  "strings"
)
const null = -1 << 31
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func buildTree(nums []int) *TreeNode {
  if len(nums) == 0 {
    return nil
  }
  root := &TreeNode{Val: nums[0]}
  Queue := []*TreeNode{root}
  idx := 1
  for idx < len(nums) {
    node := Queue[0]
    Queue = Queue[1:]
    if nums[idx] != null {
      node.Left = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Left)
    }
    idx++
    if idx < len(nums) && nums[idx] != null {
      node.Right = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Right)
    }
    idx++
  }
  return root
}
func levelOrder(root *TreeNode) [][]int {
  res := [][]int{}
  if root == nil {
    return res
  }
  Queue := []*TreeNode{root}
  for len(Queue) > 0 {
    level := []int{}
    n := len(Queue)
    for i := 0; i < n; i++ {
      cur := Queue[0]
      Queue = Queue[1:]
      level = append(level, cur.Val)
      if cur.Left != nil {
        Queue = append(Queue, cur.Left)
      }
      if cur.Right != nil {
        Queue = append(Queue, cur.Right)
      }
    }
    res = append(res, level)
  }
  return res
}
func Array2DToString(array [][]int) string {
  if len(array) == 0 {
    return "[]"
  }
  arr2str := func(arr []int) string {
    res := "["
    for i := 0; i < len(arr); i++ {
      res += fmt.Sprint(arr[i])
      if i != len(arr)-1 {
        res += ","
      }
    }
    return res + "]"
  }
  res := make([]string, len(array))
  for i, arr := range array {
    res[i] = arr2str(arr)
  }
  return strings.Join(strings.Fields(fmt.Sprint(res)), ",")
}
func kthSmallest(root *TreeNode, k int) int {
  var res []int
  var inorder func(node *TreeNode)
  inorder = func(node *TreeNode) {
    if node == nil {
      return
    }
    inorder(node.Left)
    res = append(res, node.Val)
    inorder(node.Right)
  }
  inorder(root)
  return res[k-1]
}
func main() {
  nums := []int{3, 1, 4, null, 2}
  root := buildTree(nums)
  fmt.Println(Array2DToString(levelOrder(root)))
  fmt.Println(kthSmallest(root, 1))
  nums = []int{5, 3, 6, 2, 4, null, null, 1}
  root = buildTree(nums)
  fmt.Println(Array2DToString(levelOrder(root)))
  fmt.Println(kthSmallest(root, 3))
}

代码2：中序遍历增加一个计数器 count 统计遍历到的节点个数，如果 count 等于 k，就返回当前节点值。

package main
import (
  "fmt"
  "strings"
)
const null = -1 << 31
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func buildTree(nums []int) *TreeNode {
  if len(nums) == 0 {
    return nil
  }
  root := &TreeNode{Val: nums[0]}
  Queue := []*TreeNode{root}
  idx := 1
  for idx < len(nums) {
    node := Queue[0]
    Queue = Queue[1:]
    if nums[idx] != null {
      node.Left = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Left)
    }
    idx++
    if idx < len(nums) && nums[idx] != null {
      node.Right = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Right)
    }
    idx++
  }
  return root
}
func levelOrder(root *TreeNode) [][]int {
  res := [][]int{}
  if root == nil {
    return res
  }
  Queue := []*TreeNode{root}
  for len(Queue) > 0 {
    level := []int{}
    n := len(Queue)
    for i := 0; i < n; i++ {
      cur := Queue[0]
      Queue = Queue[1:]
      level = append(level, cur.Val)
      if cur.Left != nil {
        Queue = append(Queue, cur.Left)
      }
      if cur.Right != nil {
        Queue = append(Queue, cur.Right)
      }
    }
    res = append(res, level)
  }
  return res
}
func Array2DToString(array [][]int) string {
  if len(array) == 0 {
    return "[]"
  }
  arr2str := func(arr []int) string {
    res := "["
    for i := 0; i < len(arr); i++ {
      res += fmt.Sprint(arr[i])
      if i != len(arr)-1 {
        res += ","
      }
    }
    return res + "]"
  }
  res := make([]string, len(array))
  for i, arr := range array {
    res[i] = arr2str(arr)
  }
  return strings.Join(strings.Fields(fmt.Sprint(res)), ",")
}
func kthSmallest(root *TreeNode, k int) int {
  stack := []*TreeNode{}
  count := 0
  node := root
  for node != nil || len(stack) > 0 {
    for node != nil {
      stack = append(stack, node)
      node = node.Left
    }
    node = stack[len(stack)-1]
    stack = stack[:len(stack)-1]
    count++
    if count == k {
      return node.Val
    }
    node = node.Right
  }
  return 0
}
func main() {
  nums := []int{3, 1, 4, null, 2}
  root := buildTree(nums)
  fmt.Println(Array2DToString(levelOrder(root)))
  fmt.Println(kthSmallest(root, 1))
  nums = []int{5, 3, 6, 2, 4, null, null, 1}
  root = buildTree(nums)
  fmt.Println(Array2DToString(levelOrder(root)))
  fmt.Println(kthSmallest(root, 3))
}

代码3：用stack迭代

package main
import (
  "fmt"
  "strings"
)
const null = -1 << 31
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func buildTree(nums []int) *TreeNode {
  if len(nums) == 0 {
    return nil
  }
  root := &TreeNode{Val: nums[0]}
  Queue := []*TreeNode{root}
  idx := 1
  for idx < len(nums) {
    node := Queue[0]
    Queue = Queue[1:]
    if nums[idx] != null {
      node.Left = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Left)
    }
    idx++
    if idx < len(nums) && nums[idx] != null {
      node.Right = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Right)
    }
    idx++
  }
  return root
}
func levelOrder(root *TreeNode) [][]int {
  res := [][]int{}
  if root == nil {
    return res
  }
  Queue := []*TreeNode{root}
  for len(Queue) > 0 {
    level := []int{}
    n := len(Queue)
    for i := 0; i < n; i++ {
      cur := Queue[0]
      Queue = Queue[1:]
      level = append(level, cur.Val)
      if cur.Left != nil {
        Queue = append(Queue, cur.Left)
      }
      if cur.Right != nil {
        Queue = append(Queue, cur.Right)
      }
    }
    res = append(res, level)
  }
  return res
}
func Array2DToString(array [][]int) string {
  if len(array) == 0 {
    return "[]"
  }
  arr2str := func(arr []int) string {
    res := "["
    for i := 0; i < len(arr); i++ {
      res += fmt.Sprint(arr[i])
      if i != len(arr)-1 {
        res += ","
      }
    }
    return res + "]"
  }
  res := make([]string, len(array))
  for i, arr := range array {
    res[i] = arr2str(arr)
  }
  return strings.Join(strings.Fields(fmt.Sprint(res)), ",")
}
func kthSmallest(root *TreeNode, k int) int {
    stack := []*TreeNode{}
    count := 0
    node := root
    for node != nil || len(stack) > 0 {
        for node != nil {
            stack = append(stack, node)
            node = node.Left
        }
        node = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        count++
        if count == k {
            return node.Val
        }
        node = node.Right
    }
    return 0
}
func main() {
  nums := []int{3, 1, 4, null, 2}
  root := buildTree(nums)
  fmt.Println(Array2DToString(levelOrder(root)))
  fmt.Println(kthSmallest(root, 1))
  nums = []int{5, 3, 6, 2, 4, null, null, 1}
  root = buildTree(nums)
  fmt.Println(Array2DToString(levelOrder(root)))
  fmt.Println(kthSmallest(root, 3))
}

输出：

[[3],[1,4],[2]]

1

[[5],[3,6],[2,4],[1]]

3

235. 二叉搜索树的最近公共祖先 Lowest Common Ancestor of a BST

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8

输出: 6

解释: 节点 2 和节点 8 的最近公共祖先是 6。


示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4

输出: 2

解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。


说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉搜索树中。

代码1： 迭代

package main
import (
  "fmt"
  "strings"
)
const null = -1 << 31
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func buildTree(nums []int) *TreeNode {
  if len(nums) == 0 {
    return nil
  }
  root := &TreeNode{Val: nums[0]}
  Queue := []*TreeNode{root}
  idx := 1
  for idx < len(nums) {
    node := Queue[0]
    Queue = Queue[1:]
    if nums[idx] != null {
      node.Left = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Left)
    }
    idx++
    if idx < len(nums) && nums[idx] != null {
      node.Right = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Right)
    }
    idx++
  }
  return root
}
func levelOrder(root *TreeNode) [][]int {
  res := [][]int{}
  if root == nil {
    return res
  }
  Queue := []*TreeNode{root}
  for len(Queue) > 0 {
    level := []int{}
    n := len(Queue)
    for i := 0; i < n; i++ {
      cur := Queue[0]
      Queue = Queue[1:]
      level = append(level, cur.Val)
      if cur.Left != nil {
        Queue = append(Queue, cur.Left)
      }
      if cur.Right != nil {
        Queue = append(Queue, cur.Right)
      }
    }
    res = append(res, level)
  }
  return res
}
func Array2DToString(array [][]int) string {
  if len(array) == 0 {
    return "[]"
  }
  arr2str := func(arr []int) string {
    res := "["
    for i := 0; i < len(arr); i++ {
      res += fmt.Sprint(arr[i])
      if i != len(arr)-1 {
        res += ","
      }
    }
    return res + "]"
  }
  res := make([]string, len(array))
  for i, arr := range array {
    res[i] = arr2str(arr)
  }
  return strings.Join(strings.Fields(fmt.Sprint(res)), ",")
}
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
  node := root
  for node != nil {
    if p.Val < node.Val && q.Val < node.Val {
      node = node.Left
    } else if p.Val > node.Val && q.Val > node.Val {
      node = node.Right
    } else {
      return node
    }
  }
  return nil
}
func main() {
  nums := []int{6, 2, 8, 0, 4, 7, 9, null, null, 3, 5}
  root := buildTree(nums)
  p, q := &TreeNode{Val: 2}, &TreeNode{Val: 8}
  fmt.Println(Array2DToString(levelOrder(root)))
  fmt.Println(lowestCommonAncestor(root, p, q).Val)
  q = &TreeNode{Val: 4}
  fmt.Println(lowestCommonAncestor(root, p, q).Val)
}

代码2： 递归

package main
import (
  "fmt"
  "strings"
)
const null = -1 << 31
type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
func buildTree(nums []int) *TreeNode {
  if len(nums) == 0 {
    return nil
  }
  root := &TreeNode{Val: nums[0]}
  Queue := []*TreeNode{root}
  idx := 1
  for idx < len(nums) {
    node := Queue[0]
    Queue = Queue[1:]
    if nums[idx] != null {
      node.Left = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Left)
    }
    idx++
    if idx < len(nums) && nums[idx] != null {
      node.Right = &TreeNode{Val: nums[idx]}
      Queue = append(Queue, node.Right)
    }
    idx++
  }
  return root
}
func levelOrder(root *TreeNode) [][]int {
  res := [][]int{}
  if root == nil {
    return res
  }
  Queue := []*TreeNode{root}
  for len(Queue) > 0 {
    level := []int{}
    n := len(Queue)
    for i := 0; i < n; i++ {
      cur := Queue[0]
      Queue = Queue[1:]
      level = append(level, cur.Val)
      if cur.Left != nil {
        Queue = append(Queue, cur.Left)
      }
      if cur.Right != nil {
        Queue = append(Queue, cur.Right)
      }
    }
    res = append(res, level)
  }
  return res
}
func Array2DToString(array [][]int) string {
  if len(array) == 0 {
    return "[]"
  }
  arr2str := func(arr []int) string {
    res := "["
    for i := 0; i < len(arr); i++ {
      res += fmt.Sprint(arr[i])
      if i != len(arr)-1 {
        res += ","
      }
    }
    return res + "]"
  }
  res := make([]string, len(array))
  for i, arr := range array {
    res[i] = arr2str(arr)
  }
  return strings.Join(strings.Fields(fmt.Sprint(res)), ",")
}
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if p.Val < root.Val && q.Val < root.Val {
        return lowestCommonAncestor(root.Left, p, q)
    } else if p.Val > root.Val && q.Val > root.Val {
        return lowestCommonAncestor(root.Right, p, q)
    } else {
        return root
    }
}
func main() {
  nums := []int{6, 2, 8, 0, 4, 7, 9, null, null, 3, 5}
  root := buildTree(nums)
  p, q := &TreeNode{Val: 2}, &TreeNode{Val: 8}
  fmt.Println(Array2DToString(levelOrder(root)))
  fmt.Println(lowestCommonAncestor(root, p, q).Val)
  q = &TreeNode{Val: 4}
  fmt.Println(lowestCommonAncestor(root, p, q).Val)
}

输出：

[[6],[2,8],[0,4,7,9],[3,5]]

6

2

🌟 每日一练刷题专栏 🌟

✨持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！

🌟 收藏，你的青睐是我努力的方向！

✎ 评论，你的意见是我进步的财富！  

☸ 主页：https://hannyang.blog.csdn.net/

 Rust每日一练 专栏

（2023.5.16~）更新中...

Golang每日一练 专栏

（2023.3.11~）更新中...

Python每日一练 专栏

（2023.2.18~2023.5.18）暂停更

C/C++每日一练 专栏

（2023.2.18~2023.5.18）暂停更

Java每日一练 专栏

（2023.3.11~2023.5.18）暂停更


文章标签：
算法
Java
C++
Go
Rust
关键词：
Python子串
Golang元素
HannYang
目录
相关文章
家和万事兴..
|
5天前
|
数据挖掘 开发者 Python
Python：字符串判断子串
Python：字符串判断子串
家和万事兴..
21 0
HannYang
|
5天前
|
Shell Linux 算法
Shell编程——弱数据类型的脚本语言快速入门指南
Shell编程——弱数据类型的脚本语言快速入门指南
HannYang
58 0
Shell编程——弱数据类型的脚本语言快速入门指南
HannYang
|
5天前
|
Go Linux Shell
Linux 终端命令之文件浏览(2) more
Linux 终端命令之文件浏览(2) more
HannYang
34 0
Linux 终端命令之文件浏览(2) more
HannYang
|
5天前
|
Shell 机器学习/深度学习 Linux
Linux 终端操作命令（2）内部命令
Linux 终端操作命令（2）内部命令
HannYang
25 0
Linux 终端操作命令（2）内部命令
HannYang
|
5天前
|
C++ 算法 存储
力扣 C++｜一题多解之动态规划专题（2）
力扣 C++｜一题多解之动态规划专题（2）
HannYang
40 0
力扣 C++｜一题多解之动态规划专题（2）
长梦
|
5天前
|
监控 算法 Go
Golang深入浅出之-Go语言中的服务熔断、降级与限流策略
【5月更文挑战第4天】本文探讨了分布式系统中保障稳定性的重要策略：服务熔断、降级和限流。服务熔断通过快速失败和暂停故障服务调用来保护系统；服务降级在压力大时提供有限功能以保持整体可用性；限流控制访问频率，防止过载。文中列举了常见问题、解决方案，并提供了Go语言实现示例。合理应用这些策略能增强系统韧性和可用性。
长梦
55 0
长梦
|
5天前
|
分布式计算 Java Go
Golang深入浅出之-Go语言中的分布式计算框架Apache Beam
【5月更文挑战第6天】Apache Beam是一个统一的编程模型，适用于批处理和流处理，主要支持Java和Python，但也提供实验性的Go SDK。Go SDK的基本概念包括`PTransform`、`PCollection`和`Pipeline`。在使用中，需注意类型转换、窗口和触发器配置、资源管理和错误处理。尽管Go SDK文档有限，生态系统尚不成熟，且性能可能不高，但它仍为分布式计算提供了可移植的解决方案。通过理解和掌握Beam模型，开发者能编写高效的数据处理程序。
长梦
142 1
长梦
|
5天前
|
缓存 测试技术 持续交付
Golang深入浅出之-Go语言中的持续集成与持续部署（CI/CD）
【5月更文挑战第5天】本文介绍了Go语言项目中的CI/CD实践，包括持续集成与持续部署的基础知识，常见问题及解决策略。测试覆盖不足、版本不一致和构建时间过长是主要问题，可通过全面测试、统一依赖管理和利用缓存优化。文中还提供了使用GitHub Actions进行自动化测试和部署的示例，强调了持续优化CI/CD流程以适应项目需求的重要性。
长梦
57 1
长梦
|
5天前
|
Kubernetes Cloud Native Go
Golang深入浅出之-Go语言中的云原生开发：Kubernetes与Docker
【5月更文挑战第5天】本文探讨了Go语言在云原生开发中的应用，特别是在Kubernetes和Docker中的使用。Docker利用Go语言的性能和跨平台能力编写Dockerfile和构建镜像。Kubernetes，主要由Go语言编写，提供了方便的客户端库与集群交互。文章列举了Dockerfile编写、Kubernetes资源定义和服务发现的常见问题及解决方案，并给出了Go语言构建Docker镜像和与Kubernetes交互的代码示例。通过掌握这些技巧，开发者能更高效地进行云原生应用开发。
长梦
58 1
长梦
|
5天前
|
负载均衡 监控 Go
Golang深入浅出之-Go语言中的服务网格（Service Mesh）原理与应用
【5月更文挑战第5天】服务网格是处理服务间通信的基础设施层，常由数据平面（代理，如Envoy）和控制平面（管理配置）组成。本文讨论了服务发现、负载均衡和追踪等常见问题及其解决方案，并展示了使用Go语言实现Envoy sidecar配置的例子，强调Go语言在构建服务网格中的优势。服务网格能提升微服务的管理和可观测性，正确应对问题能构建更健壮的分布式系统。
长梦
30 1

热门文章

最新文章

  • 1
    Golang框架实战-KisFlow流式计算框架(2)-项目构建/基础模块-(上)
  • 2
    Golang框架实战-KisFlow流式计算框架(1)-概述
  • 3
    单元测试3.0实践之Golang质量生态建设
  • 4
    Golang深入浅出之-切片（Slices）入门：创建、操作与扩容机制
  • 5
    Golang深入浅出之-Go语言结构体（struct）入门：定义与使用
  • 6
    Golang深入浅出之-Go语言函数基础：定义、调用与多返回值
  • 7
    Golang深入浅出之-Go语言中的时间与日期处理：time包详解
  • 8
    Golang深入浅出之-文件与目录操作：os与path/filepath包
  • 9
    Golang深入浅出之-Go数据类型详解：整型、浮点型与布尔型
  • 10
    Golang深入浅出之-Go语言基础语法：变量声明与赋值
  • 1
    请简述Python中的垃圾回收机制。
    15
  • 2
    Python中如何实现二分查找？请提供代码示例。
    26
  • 3
    Python中如何实现列表去重？请提供至少两种方法
    21
  • 4
    Python中的装饰器：概念、用法和实例
    23
  • 5
    Python中的装饰器：概念、用法及实例
    19
  • 6
    使用Python实现图像处理中的边缘检测算法
    99
  • 7
    Python中如何实现字符串反转？请提供至少两种方法。
    26
  • 8
    在Python中，如何创建一个迭代器？
    22
  • 9
    请解释Python中的迭代器和生成器的区别？并分别举例说明。
    21
  • 10
    在Python中，如何使用装饰器重写类的方法？
    293

    • 相关课程

    更多
  • Python Web开发基础
  • Python开发基础入门
  • Python常用数据科学库
  • Python网络爬虫实战
  • Python完全自学手册图文教程
  • Python基础快速入门实战教程

    • 相关电子书

    更多
  • From Python Scikit-Learn to Sc
  • Data Pre-Processing in Python:
  • 双剑合璧-Python和大数据计算平台的结合

    • 相关实验场景

    更多
  • 用Python画圣诞树
  • 使用Python完成RDS数据开发及分析
  • Python选择及循环结构
  • 云端Python及基本操作
  • Python网络通信程序典型应用
  • Python新手入门（Anolis OS）

    • 推荐镜像

    更多
  • golang
  • nodejs-release
  • pypi
    • 下一篇
    2024年阿里云免费云服务器及学生云服务器申请教程参考