105. Construct Binary Tree from Preorder and Inorder Traversal.md

105. Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Solution

递归可以解决，preorder的第一个（比如3）总是root，然后再inorder里面找到3的位置，前面是left，右面是right，递归进行即可。

code1是自己写的

code2是看了discussion以后改进的

code3是java版本的

Code1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if len(preorder)==0:
            root = None
        elif len(preorder)==1:
            root = TreeNode(preorder[0])
        else:
            root_val = preorder[0]
            index = inorder.index(root_val)
            root = TreeNode(root_val)
            root.left = self.buildTree(preorder[1:index+1],inorder[:index])
            root.right = self.buildTree(preorder[index+1:],inorder[index+1:])
        return root

Code2

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """        
        if len(inorder)==0:
            root = None
        else:
            root_val = preorder.pop(0)
            index = inorder.index(root_val)
            root = TreeNode(root_val)
            root.left = self.buildTree(preorder,inorder[:index])
            root.right = self.buildTree(preorder,inorder[index+1:])
        return root

Code3

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private TreeNode helper(int[] preorder, int[] inorder, int prest, int preed, int inst, int ined)
    {
        // System.out.printf("[%d,%d],[%d,%d]\n",prest,preed,inst,ined);
        if(prest > preed || preed >= preorder.length)
            return null;
        
        TreeNode root = new TreeNode(preorder[prest]);
        
        if(prest == preed)
            return root;
        
        int idx = -1;
        for(int i=inst;i<=ined;i++)
        {
            if(inorder[i] == root.val)
            {
                idx = i;
                break;
            }
        }
        
        root.left  = helper(preorder,inorder,prest+1,prest+idx-inst,inst,idx-1);
        root.right = helper(preorder,inorder,prest+idx-inst+1,preed,idx+1,ined);
        return root;       
    }
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return helper(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);       
    }
}