【题目】给定一颗二叉搜索树，请找出其中的第k大的结点。
* 例如， 5
* / \
* 3 7
* / \ / \
* 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。 中序遍历：2 3 4 5 6 7 8
package com.exe7.offer; import java.util.Stack; /**
* 【题目】给定一颗二叉搜索树，请找出其中的第k大的结点。
* 例如， 5
* / \
* 3 7
* / \ / \
* 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。 中序遍历：2 3 4 5 6 7 8
* @author WGS
*
*/
public class BiTreeKthNode {
static class TreeNode{
int val;
TreeNode left=null;
TreeNode right=null;
public TreeNode(int val){
this.val=val;
}
} public TreeNode getKthNode(TreeNode pRoot,int k){
if(pRoot==null ) return pRoot;
TreeNode curNode=pRoot;
Stack<TreeNode> stack=new Stack<>();
int p=0; while(curNode!=null || !stack.isEmpty()){
while(curNode!=null){
stack.push(curNode);
curNode=curNode.left;
}
if(!stack.isEmpty()){
curNode=stack.pop();
p++;
if(p==k) return curNode;
curNode=curNode.right;
}
}
return null;
} public static void main(String[] args) { BiTreeKthNode b=new BiTreeKthNode();
TreeNode root=new TreeNode(5);
TreeNode node1=new TreeNode(3);
TreeNode node2=new TreeNode(7);
TreeNode node3=new TreeNode(2);
TreeNode node4=new TreeNode(4);
TreeNode node5=new TreeNode(6);
TreeNode node6=new TreeNode(8);
root.left=node1;
root.right=node2;
node1.left=node3;
node1.right=node4;
node2.left=node5;
node2.right=node6; TreeNode node=b.getKthNode(root, 2);
System.out.println(node.val);
} }