二叉树后序算法（二分）

迈不过友情╰ 2022-11-05 08:49 44阅读 0赞

给定一个数组\[2,4,3,6,8,7,5\],遍历后使得  
此Node->left小于此节点  
此Node->right大于此节点

下列代码为后序遍历，时间复杂度为O(N^2)

public class tree{
        
    	public static class Node{
        
    		public int val;
    		public int left;
    		public int right;
    		public Node(int v){
        val = v;
    		}
    		
    	public static Node arrayToBST(int[] arr){
        
    		//array, begin range, end range
    		return flatten(arr, 0, arr.length-1);
    	}
    	
    	public static Node flatten(int[] arr, int L, int R){
        
    		//We need to check if L is passed by R
    		if(L > R){
        return null}
    
    		Node head = new Node(arr[R]);
    		
    		//if left equals to right that means only one value here
    		if(L==R){
        return head;}
    		
    		//Check where is the middle value, L-1 indicates the tree only have right side, which is the beginning of left side M=0-1+1
    		int M = L-1;
    		//keep looking to find the middle position if both side equals
    		for(int i = L; i<R; ++i){
        
    			if(arr[i]<arr[R]){
        
    				M = i;
    			}
    		}
    		flatten(arr, L, M);
    		flatten(arr, M+1, R-1);
    	}
    	return head;
    }

可以用二分法来进行优化  
下列代码时间复杂度为O(logN)

int left = L;
    int right = R-1;
    int M = L - 1;
    while(left<=right){
        
    	int mid = left + ((right-left)>>1);
    	if(arr[mid]<arr[R]){
        
    		M = mid;
    		left = mid + 1;
    	}else{
        
    		right = mid - 1;
    	}
    }