54. 二叉查找树的第 K 个结点

Leetcode

题目描述

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

解题思路

二叉查找树的中序遍历（左-根-右）为升序序列，而逆中序遍历（右-根-左）即为降序序列。利用逆中序遍历访问到第 cnt 个节点即为目标值。

private int val;
private int count = 0;

public int findTargetNode(TreeNode root, int cnt) {
    count = 0;
    inOrder(root, cnt);
    return val;
}

private void inOrder(TreeNode root, int cnt) {
    if (root == null || count >= cnt) {
        return;
    }
    inOrder(root.right, cnt);
    count++;
    if (count == cnt) {
        val = root.val;
    }
    inOrder(root.left, cnt);
}