您现在的位置是：首页 > 文章详情

算法篇：树之倒数k个节点

日期：2020-08-13点击：423收藏

算法：

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

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

题目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 }