二叉搜索树找出其中的第k小的结点(思路)

KLQ 2020-04-13 10:53:01 java常见问答 8512

下面给大家分享的是给定一棵二叉搜索树,找出其中的第k小的结点的思路,一共分享了3种思路,思路2和思路3是一看就懂的,大家可以具体的看一下吧。

给定一棵二叉搜索树,请找出其中的第k小的结点。

例:

 (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。

思路1:

//思路:二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。
//     所以,按照中序遍历顺序找到第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;
    }
}

思路2:

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;
    }
}

思路3:

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;
    }
}

以上就是具体的一些思路啦,大家都了解了吗?更多相关java实例,请继续来本站了解吧。