package Exercises;

import java.util.ArrayList;
import java.util.Stack;

/*
 * 给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。
 */
public class Test57 {
       public int KthNode(TreeNode pRoot,int k){
    	     return Search2(pRoot).get(k-1);    	   
       }
       
       //递归算法
       public ArrayList<Integer> Search1(TreeNode pRoot){
    	   ArrayList<Integer> sort=new ArrayList<>();
    	   if(pRoot==null){
    		   return sort;
    	   }
    	   //中序遍历得到从小到大的数的排列
    	   //递归算法
    	  if(pRoot!=null){
    		   sort.addAll(Search1(pRoot.left));
    		   sort.add(pRoot.val);
    		   sort.addAll(Search1(pRoot.right));   		   
    	  }
    	   return sort;
       }
       
       //非递归算法
       public ArrayList<Integer> Search2(TreeNode pRoot){
    	   TreeNode currentNode=null;
    	   ArrayList<Integer> sort=new ArrayList<>();
    	   if(pRoot==null){
    		   return sort;
    	   }
    	   if(pRoot!=null){
    	   
    		   Stack<TreeNode> S=new Stack<>();
    		   S.push(pRoot);  //根节点入栈
    		   while(!S.isEmpty()){
    			   //将根节点的左孩子依次入栈
    			   while(S.peek()!=null){
    				   S.push(S.peek().left);
    			   }
    			   S.pop();//空节点退栈
    			   
    			   if(!S.isEmpty()){
    				   currentNode=S.pop();
    				   sort.add(currentNode.val);
    				   S.push(currentNode.right);
    			   }   
    		   }
    		  
    	 }
    	   return sort;
       }
       
       public static void main(String args[]){
   		 Test57 t=new Test57();
   		 TreeNode ndoe4=new TreeNode(4);
   		 TreeNode ndoe2=new TreeNode(2);
   		 TreeNode ndoe6=new TreeNode(6);
   		 TreeNode ndoe8=new TreeNode(8);
   		 TreeNode node7=new TreeNode(7,ndoe6,ndoe8);
   		 TreeNode node3=new TreeNode(3,ndoe2,ndoe4);
   		 TreeNode root=new TreeNode(5,node3,node7);
   		 System.out.println(t.KthNode(root, 3));
   	}
}