Java 实现二叉树排序树第k个节点

Java 实现二叉树排序树第k个节点 Java 实现二叉树排序树第k个节点

需要用到二叉搜搜索数的性质：中序遍历之后得到的值是递增的顺序

import java.util.ArrayList;

public class Solution {
	
	
    public int KthNode (TreeNode proot, int k) {
    	
    	if (proot == null||k==0) return -1;
    	
    	// 1.定义集合：存储数据 - 此时集合中存储的数据是 递增的
    	ArrayList trrIntegers = middleOrder(proot, new ArrayList());
    	
    	if (k>trrIntegers.size()) return -1;
    	
    	// 2.返回数据
    	return trrIntegers.get(k-1);
    }
    
    
    
    public ArrayList middleOrder(TreeNode parentNode,ArrayList integers){
    	
    	if (parentNode == null) return null;
    	
    	middleOrder(parentNode.left, integers);
    	
    	integers.add(parentNode.val);
    	
    	middleOrder(parentNode.right, integers);
    	
    	return integers;
    }
}