二叉搜索树的第 K 个结点

题目描述

给定一颗二叉搜索树，请找出其中的第 k 大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为 4。

解题思路

按照中序遍历，第 K 个结点就是第 K 大的结点。

可以用栈或者用递归。

代码

代码 1

import java.util.Stack;
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k) {
        Stack<TreeNode> stack = new Stack<>();
        while (pRoot != null || !stack.isEmpty()) {
            while (pRoot != null) {
                stack.push(pRoot);
                pRoot = pRoot.left;
            }
            pRoot = stack.pop();
            k--;
            if (k == 0)
                return pRoot;
            pRoot = pRoot.right;
        }
        return null;
    }
}

代码 2

public class Solution {
    private int index = 0;
    TreeNode KthNode(TreeNode pRoot, int k) {
        if (pRoot != null) {
            TreeNode node = KthNode(pRoot.left, k);
            if (node != null)
                return node;
            index++;
            if (index == k)
                return pRoot;
            node = KthNode(pRoot.right, k);
            if (node != null)
                return node;
        }
        return null;
    }
}