54. 二叉搜索树的第k大节点【中序遍历】

1. 问题

给定一棵二叉搜索树，请找出其中第k大的节点。

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4

限制：

1 ≤ k ≤ 二叉搜索树元素个数

2. 解法 - 中序遍历

2.1 Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int ans, K;
    public int kthLargest(TreeNode root, int k) {
        // K作为全局变量使用
        K = k;
        // 对二叉搜索树进行中序遍历
        dfs(root);
        // 返回结果
        return ans;
    }

    // 求 “二叉搜索树第 k 大的节点” 可转化为求 “此树的中序遍历倒序的第 k 个节点”。
    // 中序遍历倒序的遍历：右根左
    public void dfs(TreeNode root) {
        if (root == null)
            return;

        // 右
        dfs(root.right);

        // 找到了第k大的元素，记录下来，返回即可
        if (--K == 0) {
            ans = root.val;
            return;
        }

        // 左
        dfs(root.left);
    }
}

2.2 Kotlin

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    var ans: Int = 0
    var kk: Int = 0
    fun kthLargest(root: TreeNode, k: Int): Int {
        // kk作为全局变量使用
        kk = k
        // 对二叉搜索树进行中序遍历
        dfs(root)
        // 返回结果
        return ans
    }

    // 求 “二叉搜索树第 k 大的节点” 可转化为求 “此树的中序遍历倒序的第 k 个节点”。
    // 中序遍历倒序的遍历：右根左
    fun dfs(root: TreeNode?) {
        if (root == null)
            return

        // 右
        dfs(root.right)

        // 找到了第k大的元素，记录下来
        if (--kk == 0)
            ans = root.`val`

        // kk已经找到了，返回即可
        if (kk == 0)
            return

        // 左
        dfs(root.left)
    }
}

3. 参考

4. 笔记

上一页53 - II. 0～n-1中缺失的数字【二分查找/位运算】下一页55 - I. 二叉树的深度【DFS/BFS】

最后更新于3年前