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

灰子学技术

发布于 2020-08-17 15:19:53

3260

发布于 2020-08-17 15:19:53

文章被收录于专栏：灰子学技术灰子学技术

算法：

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

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

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

执行结果：