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

题目描述

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

解题思路

• 二叉搜索树有这样的特性
  • 左子树所有节点都比跟节点小，右子树所有节点都比跟节点大。
  • 中序遍历正好是从小到大遍历的。
  • 中序遍历后，取倒数第k个节点就是答案了。

public class Solution {
    public int kthLargest(TreeNode root, int k) {
        final ArrayList<Integer> nodeVal = new ArrayList<>();
        InorderTrans(root, nodeVal);
        return nodeVal.get(nodeVal.size() - k);
    }

    public void InorderTrans(TreeNode root, List<Integer> nodeVal) {
        TreeNode left = root.left;
        if (left != null) {
            InorderTrans(left, nodeVal);
        }
        nodeVal.add(root.val);
        TreeNode right = root.right;
        if (right != null) {
            InorderTrans(right, nodeVal);
        }
    }
}

效果似乎不太理想