my java recursion solution divide and conquer-very easy to understand-Chinese notes


  • 1
    G
    public class Solution {
       public TreeNode buildTree(int[] inorder, int[] postorder) {
            //我的思路是Post的最后一个数就是当前的root,然后在inorder里面找到这个root的index,再把inorder和postorder数组根据这个index各分为两半,再迭代继续找
            int len=inorder.length;
            if(len==0)
            {
                return null;
            }
            
            int val=postorder[len-1];
         
            TreeNode root = new TreeNode(val);//Post的最后一个数就是当前的root
            
            int index =findindex(inorder, val);//在inorder里面找到这个数的index
            
            
            int [] leftinorder=new int[index];//把inorder和postorder分为两半,在前面那一半找root.left
            int [] leftpost=new int[index];
            
            leftinorder = Arrays.copyOfRange(inorder, 0, index);
            leftpost = Arrays.copyOfRange(postorder, 0, index);
            
            int [] rightinorder = new int[len-1-index];//把inorder和postorder分为两半,在后面那一半找root.right
            int [] rightpost = new int [len-1-index];
            
            rightinorder = Arrays.copyOfRange(inorder,index+1,len);
            rightpost = Arrays.copyOfRange(postorder,index,len-1);
            
            
            root.left=buildTree(leftinorder,leftpost);
            root.right=buildTree(rightinorder,rightpost);
            
            return root;
        }
        
        public int findindex(int [] arr, int target)//找index的方法,此时不能用Arrays.binarySearch,因为数组没有sort.
        {
            int len =arr.length;
            for(int i=0;i<len;i++)
            {
                if(arr[i]==target)
                {
                    return i;
                }
            }
            return -1;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.