灰子学算法之树的倒数k个节点

灰子学算法之树的倒数k个节点算法 这类题目的核心思想是 利用二叉树的中序遍历是从小到大的 将其转变成数组 然后对这个有序数组进行取值操作就可以了 特别注意 转换之后的数组有可能会存在重复的节点 此时的话 我们就需要对数组进行去重的操作 题目 1 https leetcode cn

大家好,我是讯享网,很高兴认识大家。

算法:

这类题目的核心思想是,利用二叉树的中序遍历是从小到大的,将其转变成数组,然后对这个有序数组进行取值操作就可以了。

特别注意:转换之后的数组有可能会存在重复的节点,此时的话,我们就需要对数组进行去重的操作。

题目1:

https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree/


讯享网

代码实现:

/ * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func findSecondMinimumValue(root *TreeNode) int { res := midOrder(root) m := make(map[int]int) for _,v:=range res { m[v] = v } resp := []int{} for _,v:=range m { resp = append(resp,v) } if len(resp)>=2{ sort.Ints(resp) return resp[1] } return -1 } func midOrder(root *TreeNode) (res []int) { if root == nil { return } res = append(res,midOrder(root.Left)...) res = append(res,root.Val) res = append(res,midOrder(root.Right)...) return } 

讯享网

执行结果:

题目2:
https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/

代码实现:

讯享网/ * 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 { return 0 } res := midOrder(root) if k > len(res) { return 0 } return res[k-1] } func midOrder(root *TreeNode) []int { if root == nil { return nil } res := []int{} res = append(res,midOrder(root.Left)...) res = append(res,root.Val) res = append(res,midOrder(root.Right)...) return res } 

执行结果:

备注:这里的算法,从执行表现来看,并不是最优的,不过这算是一种通用的解题思路。

小讯
上一篇 2025-01-06 14:37
下一篇 2025-01-05 18:25

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/82159.html