【Java】面试题54：二叉搜索树的第k大的节点

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

例如，下图中的二叉搜索树中，按节点数值大小顺序第三个节点的值 是4.

算法分析：
如果按照中序遍历的顺序遍历一棵二叉搜索树，遍历序列的数值是递增排序的。上图中的二叉搜索树的中序遍历序列为{2,3,4,5,6,7,8}，因此，只需要用中序遍历算法遍历一棵二叉搜索树，就很容易找出它的第k大结点。

方法一：递归中序遍历

package jianZhiOffer;
/*
 * 面试题54：二叉搜索树的第k个大节点
 * 题目：给定一棵二叉搜索树，请找出其中第k大的节点。
 */
public class Demo54 {
	class BinaryTreeNode{
		int val;
		BinaryTreeNode left;
		BinaryTreeNode right;
		public BinaryTreeNode(int val) {
			this.val = val;
		}
		
	}
	public static void main(String[] args) {
		Demo54 demo = new Demo54();
		BinaryTreeNode root = demo.new BinaryTreeNode(5);
		BinaryTreeNode a = demo.new BinaryTreeNode(3);
		BinaryTreeNode b = demo.new BinaryTreeNode(7);
		BinaryTreeNode c = demo.new BinaryTreeNode(2);
		BinaryTreeNode d = demo.new BinaryTreeNode(4);
		BinaryTreeNode e = demo.new BinaryTreeNode(6);
		BinaryTreeNode f = demo.new BinaryTreeNode(8);
		
		root.left = a;
		root.right = b;
		a.left = c;
		a.right = d;
		b.left = e;
		b.right = f;
		
		BinaryTreeNode k = KthNode(root,3);
		System.out.println(k.val);
	}
	
	static int index=0;
	
	static BinaryTreeNode KthNode(BinaryTreeNode pRoot,int k) {
		if(pRoot==null || k<=0)
			return null;
		return getKthNode(pRoot,k);
	}
	
	private static BinaryTreeNode getKthNode(BinaryTreeNode pRoot,int k) {
		BinaryTreeNode KthNode = null;
		if(pRoot.left != null)//如果该节点有左孩子，就一直递归到左叶子节点
			KthNode = getKthNode(pRoot.left,k);
		if(KthNode==null) {
			index++;  //中序遍历的计数
			if(k==index)
				KthNode = pRoot; 
		}
		
		if(KthNode==null && pRoot.right!=null)
			//如果该节点有右孩子，就递归到右孩子
			KthNode = getKthNode(pRoot.right,k);
		
		return KthNode;
		
	}
}

需要注意的就是递归的流程和条件。

方法二：非递归中序遍历，用栈来实现

TreeNode KthNode(BinaryTreeNode root, int k){
        if(root==null||k==0) return null;
        int count=0;
        Stack<BinaryTreeNode> stack=new Stack<>();
        while(root!=null||!stack.isEmpty()){
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root=stack.pop();
            count++;
            if(count==k) return root;
            root=root.right;
        }
        return null;
    }