🌗 剑指 Offer 54. 二叉搜索树的第k大节点

难度: 🌗

问题描述

---

解法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int top = 0;
    int res;
    public int kthLargest(TreeNode root, int k) {
        // 思路：
        // 中序遍历 - 升序
        // 变形中序遍历 - 数组降序
        mySol(root, k);
        return res;
    }

    private void mySol(TreeNode root, int k) {
        // 递归终止条件
        if(root == null) {
            return;
        }
        mySol(root.right, k);
        top ++;
        if(top == k) {
            res = root.val;
            return;
        }
        mySol(root.left, k);
    }
}

---

输出