二叉树的第k个结点

题目描述

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8）    中，按结点数值大小顺序第三小结点的值为4。

int count = 0;
TreeNode ans;
TreeNode KthNode(TreeNode pRoot, int k){
		helper(pRoot, k);
		return ans;
    }
	
public void helper(TreeNode node, int k){
		if (node==null || count>k) {
			return;
		}
		helper(node.left, k);
		count++;
		if (count == k) {
			ans = node;
		}
		helper(node.right, k);
	}

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    int i = 0;
 
    TreeNode KthNode(TreeNode pRoot, int k) {
        if (pRoot == null) {
            return null;
        }
        //中序遍历次序与大小次序相同
        TreeNode res = KthNode(pRoot.left, k);
        if (res != null) {
            return res;
        }
        i++;
        if (k == i) {
            return pRoot;
        }
        res = KthNode(pRoot.right, k);
        return res;
    }
 
 
}

 方法一：
采用递归的方式先获得中序遍历的结果，然后在从结果中找出第k个节点
代码实现如下

import java.util.ArrayList;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
//二叉搜索树的中序遍历的结果为递增数列
//先求得中序遍历的结果
public class Solution {
    public TreeNode KthNode(TreeNode pRoot, int k)
    {
        
        ArrayList<TreeNode> list = new ArrayList<>();
        inOrderRecur(pRoot,list);
        int len = list.size();
        if(k < 1 || k > len){
            return null;
        } 
        TreeNode result = list.get(k-1);
        return result;
    }
    public void inOrderRecur(TreeNode pRoot,ArrayList<TreeNode> list){
        if(pRoot == null){
            return;
        }
        inOrderRecur(pRoot.left,list);
        list.add(pRoot);
        inOrderRecur(pRoot.right,list);
    }

}

方法二：
采用方法一固然可以，但是时间复杂度过高，只能先获得中序遍历的结果才能找出位于第k个位置的节点，但是若采用非递归的方式，则可以在出栈的时候记录这个节点出栈的位次是否和要求的位置一致，若一致则直接返回该节点即可，非递归的代码实现如下：

import java.util.Stack;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
//非递归的方式实现中序遍历
public class Solution {
    public TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot == null || k < 1){
            return null;
        }
        int count = 0;
        TreeNode cur = pRoot;
        Stack<TreeNode> stack = new Stack<>();
        while(cur != null || !stack.isEmpty()){
            while( cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            count++;
            if(count == k){
                return cur;
            }
            cur = cur.right;
        }
        return null;
    }
}

自己写代码

import java.util.ArrayList;
import java.util.List;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    List<Integer> returnList = new ArrayList<>();
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot == null || k<=0){
            return null;
        }
        helper(pRoot);
        if(returnList.size() < k){
            return null;
        }
        return Find(pRoot,returnList.get(k-1));
    }
    public void helper(TreeNode pRoot){
        if(pRoot == null){
            return;
        }
        helper(pRoot.left);
        returnList.add(pRoot.val);
        helper(pRoot.right);
    }
    public TreeNode Find(TreeNode pRoot,int num){
        if(pRoot == null){
            return null;
        }
        if(pRoot.val == num){
            return pRoot;
        }
        Find(pRoot.left,num);
        Find(pRoot.right,num);
        return null;
    }
}

以上代码有一个问题就是找到了，但是不知道怎么返回