预先排序的BST的叶子节点为阵列

Question

这是我的程序，可以在预购中获得bST的叶子节点。该程序以某种方式只是打印第一片叶子，而不是全部。我尝试找到这个错误，但无法。这是程序：

     //method
    public static boolean isLeaf(int pre[], int i, int n,
        int min, int max)
         {    
           if (i >= n) 
            return false;
           if(pre[i] > min && pre[i] < max) {
            i++;
            boolean left = isLeaf(pre, i, n, min, pre[i-1]);
            boolean right = isLeaf(pre, i, n, pre[i-1], max);
            if (!right && !left) 
              System.out.println(pre[i-1] );
            return true;
     }

     return false;
      }

    //Test case:
     public static void main(String[] args){
    int preorder[] = { 890, 325, 290, 530, 965 };
    int n = preorder.length;
    int i=0;
    isLeaf( preorder,  i,  n,
            Integer.MIN_VALUE, Integer.MAX_VALUE); 
     }
     //it just prints 290, it should print 290, 530, 965 instead 

Answer 1

我敢肯定可以对此进行一些清理。而且我不是100％确定它会捕获所有角案件，但这是我的尝试。假设所有元素都是唯一的，并且严格在开放范围(Integer.MIN_VALUE, Integer.MAX_VALUE)上。

public class bst
{
    public static void print_leaves(int[] preorder)
    {
        if (preorder.length == 1)
        {
            System.out.println(preorder[0]);
        }
        else if (preorder.length > 1)
        {
            print_leaves(preorder, 0, Integer.MIN_VALUE, Integer.MAX_VALUE);
        }
    }
    public static boolean is_in_range(int min, int v, int max)
    {
        return min < v && v < max;
    }
    public static int print_leaves(int[] preorder, int i, int min, int max)
    {
        boolean in_range = is_in_range(min, preorder[i], max);
        if (i > 0 && (i == preorder.length-1 || !in_range))
        {
            if (!in_range) System.out.println(preorder[i-1]);
            if (i == preorder.length - 1) System.out.println(preorder[i]);
            return i;
        }
        boolean b = preorder[i+1] > preorder[i];
        int next = print_leaves(preorder, i+1, b ? preorder[i] : min, b ? max : preorder[i]);
        if (next == preorder.length-1 || !is_in_range(min, preorder[next], max))
        {
            return next;
        } 
        return print_leaves(preorder, next, min, max);
    }
    public static void main(String[] argv)
    {
        int[] preorder1 = { 890, 325, 290, 530, 965 };
        int[] preorder2 = { 100, 50, 25, 30, 29, 28, 75, 80, 200, 150, 250 };
        int[] preorder3 = { 0 };
        int[] preorder4 = { 100, 0, 200 };
        int[] preorder5 = { 100, 200 };
        int[] preorder6 = { 100, 50 };
        print_leaves(preorder1);
        System.out.println();
        print_leaves(preorder2);
        System.out.println();
        print_leaves(preorder3);
        System.out.println();
        print_leaves(preorder4);
        System.out.println();
        print_leaves(preorder5);
        System.out.println();
        print_leaves(preorder6);
    }
}

产生以下输出：

29053096528801502500020020050