题目描述
给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / 3 7 / / 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。
思路
利用二叉搜索数中序遍历有序的特点。
用递归和迭代分别实现中序遍历。
代码实现
package Tree;
import java.util.Stack;
/**
* 二叉搜索树的第k个结点
* 给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。
* 思路：
* 利用二叉搜索数中序遍历有序的特点。
*/
public class Solution49 {
private int cnt;
private TreeNode res;
/**
* 迭代中序遍历
*
* @param pRoot
* @param k
* @return
*/
TreeNode KthNode_2(TreeNode pRoot, int k) {
if (pRoot == null || k == 0)
return null;
int cnt = 0;
Stack<TreeNode> stack = new Stack<>();
while (pRoot != null || !stack.isEmpty()) {
while (pRoot != null) {
stack.push(pRoot);
pRoot = pRoot.left;
}
pRoot = stack.pop();
cnt++;
if (cnt == k) return pRoot;
pRoot = pRoot.right;
}
return null;
}
TreeNode KthNode(TreeNode pRoot, int k) {
inOrder(pRoot, k);
return res;
}
/**
* 递归中序遍历
*
* @param pRoot
* @param k
*/
void inOrder(TreeNode pRoot, int k) {
if (pRoot == null) return;
if (cnt > k) return;
inOrder(pRoot.left, k);
cnt++;
if (cnt == k) res = pRoot;
inOrder(pRoot.right, k);
}
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
}
转载于:https://www.cnblogs.com/wupeixuan/p/8867010.html
