前序中序/中序后续推二叉树

前序中序推二叉树

//我的做法，效率不是很好，花了31 ms。拷贝数组肯定很费时间。
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 || inorder.length == 0)
            return null;
          
        int rootVal = preorder[0];
        int rootIndex = findIndex(inorder, rootVal);
        TreeNode root = new TreeNode(rootVal);
        
        int leftNum = rootIndex;
      
        if(rootIndex == 0 )
            root.left = null;
        else
            root.left = buildTree(Arrays.copyOfRange(preorder, 1, leftNum + 1), Arrays.copyOfRange(inorder, 0, rootIndex));
        
        if(rootIndex == preorder.length)
            root.right = null;
        else
            root.right = buildTree(Arrays.copyOfRange(preorder, leftNum + 1, preorder.length), Arrays.copyOfRange(inorder, rootIndex + 1, preorder.length));
        
        return root;
    }
    
    int findIndex(int[] array, int k){
        for(int i = 0; i< array.length; i++){
            if(k == array[i])
                return i;
        }
        return -1;
    }
       
}

//detail里耗时2ms的解法
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder,0,inorder,inorder.length-1,0);
        
    }
    private TreeNode buildTree(int[] preorder,int p,int[] inorder,int start,int end){
        if(start<end || p>preorder.length-1)
            return null;
        int val = preorder[p];
        int index = start;
        for(int i=start;i>=end;i--){
            if(val==inorder[i]){
                index = i;
                break;
            }
        }
        TreeNode node = new TreeNode(val);
        node.left = buildTree(preorder,p+1,inorder,index-1,end);
        node.right = buildTree(preorder,p+(index-end)+1,inorder,start,index+1);
        return node;
    }
}

---

后序中序推二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree(postorder, postorder.length - 1, inorder, 0, inorder.length - 1);
    }
    
    TreeNode buildTree(int[] postorder, int p, int[] inorder, int start, int end){
        if(start > end || p < 0)
            return null;
        
        int val = postorder[p];
        int index = start;
        
        for(int i = start; i <= end; i++){
            if(val == inorder[i]){
                index = i;
                break;
            }
        }
        
        TreeNode node = new TreeNode(val);
        node.left = buildTree(postorder, p - (end - index) - 1, inorder, start, index - 1);
        node.right = buildTree(postorder, p-1, inorder, index + 1, end);
        return node;        
    }
    
    
}