二叉搜索树的第k个结点

2018-05-13

编程练习

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

思路：既然给定了二叉排序树，就要想到利用该树的特点，即中序遍历的结果是排好序的(从小到大)，所以只需要完成对该树的中序遍历，然后取第k-1个遍历序列中的结点即可。此处我采用了ArrayList来盛装遍历结果。

　　注意：需要判断越界情况，比如输入的k为0，或者k的值大于结果集list.size()这两种情况都应该返回null。
java代码如下：

import java.util.ArrayList;

public class KthNode {
	/**
	 * 二叉排序树中序遍历后就已经是从小到大排好序的了，所以直接取第k-1个结点就是所求
	 * @param pRoot
	 * @param k
	 * @return
	 */
    TreeNode KthNode(TreeNode pRoot, int k)
    {
    	if(k==0) {
    		return null;
    	}
    	ArrayList<TreeNode> list=new ArrayList<TreeNode>();
    	Inorder(pRoot,list);
    	if(k>list.size()) {
    		return null;
    	}
    	return list.get(k-1);
    }
    /**
     * 中序遍历排序二叉树
     * @param root
     * @param list
     */
    public static void Inorder(TreeNode root,ArrayList<TreeNode> list) {
    	if(root==null) {
    		return;
    	}
    	Inorder(root.left,list);
    	list.add(root);
    	Inorder(root.right,list);
    	
    }
    public static void main(String[] args) {
    	TreeNode root=new TreeNode(5);
		TreeNode node1=new TreeNode(3);
		TreeNode node2=new TreeNode(8);
		TreeNode node3=new TreeNode(2);
		TreeNode node4=new TreeNode(4);
		TreeNode node5=new TreeNode(7);
		
		root.left=node1;
		root.right=node2;
		node1.left=node3;
		node1.right=node4;
		node2.left=node5;
		ArrayList<TreeNode> list=new ArrayList<TreeNode>();
		Inorder(root,list);
		for(TreeNode c:list) {
			System.out.println(c.val);
		}
		
	}
}