首页 > 试题广场 > 二叉搜索树的第k个结点
[编程题]二叉搜索树的第k个结点
给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8)    中,按结点数值大小顺序第三小结点的值为4。
非递归中序遍历
TreeNode KthNode(TreeNode root, int k){
        if(root==null||k==0)
            return null;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        int count = 0;
        TreeNode node = root;
        do{
            if(node!=null){
            	stack.push(node);
                node = node.left;
            }else{
                node = stack.pop();
                count++;
                if(count==k)
                    return node;
                node = node.right;
            }
        }while(node!=null||!stack.isEmpty());
        return null;
    }

编辑于 2016-04-18 13:23:40 回复(10)
//思路:二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。
//     所以,按照中序遍历顺序找到第k个结点就是结果。
public class Solution {
   int index = 0; //计数器
	TreeNode KthNode(TreeNode root, int k)
    {
		if(root != null){ //中序遍历寻找第k个
			TreeNode node = KthNode(root.left,k);
			if(node != null)
				return node;
			index ++;
			if(index == k)
				return root;
			node = KthNode(root.right,k);
			if(node != null)
				return node;
		}
		return null;
    }
}

发表于 2016-09-10 10:39:07 回复(58)

python解法,要注意,返回的是节点,而不是节点的值!!!尼玛,被坑了。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        self.res=[]
        self.dfs(pRoot)
        return self.res[k-1] if 0<k<=len(self.res) else None
    def dfs(self,root):
        if not root:return
        self.dfs(root.left)
        self.res.append(root)
        self.dfs(root.right)
发表于 2017-10-07 19:10:49 回复(13)
class Solution {
	int count = 0;
public:
	TreeNode* KthNode(TreeNode* pRoot, unsigned int k)
	{
	    if(pRoot){	
                TreeNode *ret = KthNode(pRoot->left, k);
                if(ret) return ret;
                if(++count == k) return pRoot;
                ret = KthNode(pRoot->right,k);
                if(ret) return ret;
        }
        return nullptr;
    }
};
来一点精简的代码
发表于 2015-07-09 10:22:26 回复(33)
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    //中序遍历的结果就是有序序列,第K个元素就是vec[K-1]存储的节点指针;
    TreeNode* KthNode(TreeNode* pRoot, unsigned int k)
    {
        if(pRoot==NULL||k<=0) return NULL; 
        vector<TreeNode*> vec;
        Inorder(pRoot,vec);
        if(k>vec.size())
            return NULL;
        return vec[k-1];
    }
    //中序遍历,将节点依次压入vector中
    void Inorder(TreeNode* pRoot,vector<TreeNode*>& vec)
    {
        if(pRoot==NULL) return;
        Inorder(pRoot->left,vec);
        vec.push_back(pRoot);
        Inorder(pRoot->right,vec);
    }  
};

发表于 2016-07-26 16:16:21 回复(11)
Ron头像 Ron
import java.util.Stack;
public class Solution {
    //中序递归
    int count = 0;
	TreeNode KthNode(TreeNode pRoot, int k)
	{
		if(count > k || pRoot == null)
			return null;
		TreeNode p = pRoot;
		Stack<TreeNode> LDRStack = new Stack<TreeNode>();
		TreeNode kthNode = null;
		while(p != null || !LDRStack.isEmpty()){
			while(p != null){
				LDRStack.push(p);
				p = p.left;
			}
			TreeNode node = LDRStack.pop();
			System.out.print(node.val+",");
			count++;
			if(count == k){
				kthNode = node;
			}
			p = node.right;
		}
		return kthNode;
	}
}

发表于 2015-08-10 16:56:25 回复(8)
import java.util.*;
public class Solution {
    TreeNode KthNode(TreeNode root, int k) {
		if(root == null || k == 0) return null;
		int count = 0;
		Stack<TreeNode> 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;
	}
}

发表于 2017-07-17 03:07:07 回复(1)
/*
中序递归
*/
public class Solution {
    int count;
    TreeNode KthNode(TreeNode pRoot, int k){
        if(pRoot == null) return null;  //递归截止条件
        TreeNode node = KthNode(pRoot.left, k);
        if(node != null)  return node; // 左子树中找到符合要求的节点返回
        if(++count == k) return pRoot; // 从最左节点开始,count+1;
        node = KthNode(pRoot.right, k);
        if(node != null)  return node;//左子树中没有找到,在右子树找到了符合要求的节点返回
        return null;
    }
}
发表于 2017-03-28 11:09:24 回复(0)
public class Solution {
   	int k;
	TreeNode KthNode(TreeNode pRoot, int k) {
		this.k = k;
		return helper(pRoot);
	}

	private TreeNode helper(TreeNode pRoot) {
		TreeNode temp = null;
		if (pRoot != null) {
			if ((temp = helper(pRoot.left)) != null) return temp;
			if (--k == 0) return pRoot;	
			if ((temp = helper(pRoot.right)) != null) return temp;
		}
		return null;
	}
}

发表于 2015-08-20 14:00:30 回复(3)
//题目可能有问题吧  如果是第k大的节点,那么算出总的节点total,total-k就是第k大的节点		
TreeNode KthNode(TreeNode pRoot, int k)
			{
				//int total = getNumOfNode(pRoot);
				if (pRoot == null || k <= 0 )
					return null;
				int i = 1;
				Stack<TreeNode> stack = new Stack<TreeNode>();
				TreeNode p = pRoot;
				while (p != null || !stack.isEmpty())
					{
						while (p != null)
							{
								stack.push(p);
								p = p.left;
							}
						p = stack.pop();
						if (i++ ==k)
							return p;
						p = p.right;
					}
				return null;
			}

发表于 2015-09-03 18:31:40 回复(5)
  • 中序遍历就是一个树从小到大的排列顺序,
  • 只需要求出中序遍历到第k个元素就是所需的节点

    int index = 0;//用于记录当前访问了的节点个数
    TreeNode KthNode(TreeNode pRoot, int k) { 
        if (pRoot == null) return null;
         TreeNode l = KthNode(pRoot.left, k);
         if (l != null)  return l;
         index++;
         if (index == k) return pRoot;
         TreeNode r = KthNode(pRoot.right, k);
         if (r != null) return r;
         return null; }
编辑于 2018-08-20 14:58:03 回复(3)

typedef TreeNode* pnode;
class Solution {
    int m;
    pnode ans;
    void dfs(pnode p){
        if(!p || m < 1) return;
        dfs(p -> left);
        if(m == 1) ans = p;
        --m;
        if(m > 0) dfs(p -> right);
    }
public:
    TreeNode* KthNode(TreeNode* p, unsigned int k){
        ans = NULL; m = k;
        dfs(p);
        return ans; 
    }
};

发表于 2015-09-12 12:12:28 回复(0)
# Python 解法:中序遍历将节点存于列表,如果列表长度等于k就可以返回

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        # write code here
        if not pRoot or not k:
            return
        res = list()
        def Traversal(node):
            if len(res) >= k or not node:
                return
            Traversal(node.left)
            res.append(node)
            Traversal(node.right)
        Traversal(pRoot)
        if len(res) < k:
            return
        return res[k-1]

发表于 2018-02-17 23:44:06 回复(0)
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    int sum = 0;
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot != null){
            TreeNode node = KthNode(pRoot.left,k);
            if(node != null){
                return node;
            }
            if(++sum == k){
                return pRoot;
            }
            node = KthNode(pRoot.right,k);
            if(node != null){
                return node;
            }
        }
        return null;
    }
}

发表于 2018-08-18 16:32:48 回复(0)
public class Solution {
        int i = 0;
        TreeNode t = null;
        TreeNode KthNode(TreeNode pRoot, int k)
        {
            if (pRoot == null) return null;
            KthNode(pRoot.left, k);
            i++;
            if (i == k) t = pRoot;
             KthNode(pRoot.right, k);
             return t;
        }


}

发表于 2018-03-27 22:59:29 回复(4)
class Solution:
    # 返回对应节点TreeNode
    res = 0
    def KthNode(self, pRoot, k):
        # write code here
        if not pRoot:
            return
        left = self.KthNode(pRoot.left, k)
        self.res += 1
        if self.res == k:
            return pRoot
        right = self.KthNode(pRoot.right, k)
        if left:
            return left
        elif right:
            return right

思路中序遍历

编辑于 2018-01-30 14:08:30 回复(0)
/*
 *中序遍历二叉搜索树后正好是从小到大的顺序,直接返回第k-1个即可
 */
import java.util.ArrayList;
public class Solution {
    ArrayList<TreeNode> treenode=new ArrayList<TreeNode>();
	TreeNode KthNode(TreeNode pRoot, int k) {
		InOrder(pRoot);
        if(treenode.size()<1||k<1||k>treenode.size())
            return null;
		return treenode.get(k-1);
		
	}
	public void InOrder(TreeNode node)
	{
		if(node!=null)
		{
			InOrder(node.left);
			treenode.add(node);
			InOrder(node.right);
		}
	}
}

发表于 2017-08-24 10:24:13 回复(1)
非递归版本
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
import java.util.Stack;

public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot == null) {
            return null;
        }
        int count = 0;
        TreeNode resNode = null;
        Stack<TreeNode> stack = new Stack<>();
        while (pRoot != null || !stack.isEmpty()) {
            if(pRoot != null) {
                stack.push(pRoot);
                pRoot = pRoot.left;
            }
            else {
                count++;
                pRoot = stack.pop();
                if(count == k) {
                    resNode = pRoot;
                    break;
                }
                pRoot = pRoot.right;
            }
        }
        if(k > count) {
            return null;
        }
        return resNode;
    }
}

发表于 2018-08-14 10:38:37 回复(1)
/*题目的本质考察的是中序遍历,只是我们要维护一个记录遍历到第几个节点的变量。
在这里我们用index变量进行维护,当index==k时我们就返回该节点。下面是非递归代码
的实现形式
*/
import java.util.*;
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        Stack<TreeNode> stack=new Stack<TreeNode>();
        int index=0;
        if(pRoot==null||k==0) return null;
        while(pRoot!=null||!stack.empty()) {
            while(pRoot!=null) {
                stack.push(pRoot);
                pRoot=pRoot.left;
            }
            if(!stack.empty()) {
                pRoot=stack.pop();
                index++;
                if(index==k) return pRoot;
                pRoot=pRoot.right;
            }
        }
        return null;
    }
}

发表于 2018-05-09 09:50:19 回复(1)
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 {
    TreeNode KthNode(TreeNode pRoot, int k){
        if(k<=0||pRoot==null)	return null;
       	ArrayList<TreeNode> arr=new ArrayList<TreeNode>();
		TreeNode test=new TreeNode(-1);
		if(arr.size()==0)	arr.add(test);		
		Inorder(pRoot,arr);
        if(k>arr.size()-1)	return null;
	    return arr.get(k);
    }
    
    public void Inorder (TreeNode pRoot,ArrayList<TreeNode> arr){
		if(pRoot==null)	return;
		Inorder(pRoot.left,arr);
		arr.add(pRoot);
		Inorder(pRoot.right,arr);
	}
}

发表于 2017-05-06 20:43:48 回复(1)