面试题目试解：int数组里找二叉排序树root结点

网上看到的面试题目。

93.在一个int数组里查找这样的数，它大于等于左侧所有数，小于等于右侧所有数。
直观想法是用两个数组a、b。a[i]、b[i]分别保存从前到i的最大的数和从后到i的最小的数，

一个解答：这需要两次遍历，然后再遍历一次原数组，
将所有data[i]>=a[i-1]&&data[i]<=b[i]的data[i]找出即可。

给出这个解答后，面试官有要求只能用一个辅助数组，且要求少遍历一次。


下面是试解，当做是抛砖引玉吧。

package javabasic;

import java.util.Arrays;
import java.util.Random;

public class FindBinTreeRoot {
	/**
	 * 在一个int数组里查找这样的数，它大于等于左侧所有数，小于等于右侧所有数。
	 * 这里把数组元素看做是二叉排序树的结点，找出能作为root结点的元素。
	 * 例如：[4,2,3,5,7,4,8,9]，则8或9都可以作为root结点。
	 * @param arr 
	 * @return 目标元素的索引
	 */
	public static int find( int[] arr ) {
		// init the left max element to MIN. So any element >= it
		int lMax = Integer.MIN_VALUE;
		for ( int i = 0; i < arr.length; i++ ) {
			int cur = arr[i];
			if ( cur >= lMax ) {
				// update the left max element
				lMax = cur;
				
				boolean rightOK = true;
				// check if the right elements >= the current element
				for ( int j = i + 1; j < arr.length; j++ ) {
					// update the left max element
					if ( arr[j] >= lMax ) {
						lMax = arr[j];
					}
					
					if ( arr[j] < cur ) {
						// There is a right element < the current element,
						// so no element before index j is the possible answer.
						rightOK = false;

						// Elements after j are possible, so set current element to j
						i = j;

						break;
					}
				}

				if ( rightOK ) {
					// right the target element index
					return i;
				}
			}
		}

		return -1;
	}

	/**
	 * @param args
	 */
	public static void main( String[] args ) {
//		int[] arr = new int[]{4,2,3,5,7,4,8,9};
		//随机产生一个20个元素的数组
		int[] arr = new int[20];
		Random ran = new Random();
		int target = ran.nextInt(arr.length);
		arr[target] = 10;
		for(int i=0;i<target;i++){
			//left half <10
			arr[i] = ran.nextInt( 10 );
		}
		for(int i=target + 1;i<arr.length;i++){
			//right half > 10
			arr[i] = ran.nextInt( 10 ) + 10;
		}
		
		
		System.out.println(Arrays.toString(arr));
		System.out.println("target index=" + target);
		System.out.println("result index=" + FindBinTreeRoot.find( arr ));

	}

}

测试运行结果：
[6, 3, 7, 9, 3, 5, 9, 4, 5, 0, 1, 1, 2, 1, 3, 0, 1, 9, 10, 19]
target index=18
result index=17