LeetCode(Trees&Graphs)Construct Binary Tree from Preorder and Inorder Traversal

2018-06-22

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

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

Return the following binary tree:

思路：这道题就需要模拟人去解决通过前序和中序遍历结果来重建二叉树的算法，用递归即可，前序遍历的第一个数字是根节点，靠这个在中序序列里找到根节点，将中序遍历中的结果分成左右子树两部分，然后分别递归去生成结点即可。通过了201/203个测试用例，剩下两个巨大的测试用例没通过没找到原因，: (。

代码如下：

/**
 * 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) {
        List<Integer> prelist=new ArrayList<Integer>();
        List<Integer> inlist=new ArrayList<Integer>();
        for(int i : preorder) {
        	prelist.add(i);
        }
        for(int c : inorder) {
        	inlist.add(c);
        }
        
        return helper(prelist,inlist);
        
    }
    public TreeNode helper(List<Integer> prelist,List<Integer> inlist){
        if(prelist==null || inlist==null){
            return null;
        }
        if(prelist.size()==0 || inlist.size()==0) {
        	return null;
        }
        int prelen = prelist.size();
        int inlen = inlist.size();
        int rtvalue = prelist.get(0);
        TreeNode root=new TreeNode(rtvalue);
        int i=0;
        while(i<inlen && inlist.get(i)!=prelist.get(0)){
            i++;
        }
        List<Integer> lsub=inlist.subList(0,i);
        List<Integer> rsub=null;
        
        if(i<inlen-1){
            rsub=inlist.subList(i+1,inlen);
        }else{
            rsub=null;
        }
        prelist.remove(0);
        root.left=helper(prelist,lsub);
        root.right=helper(prelist,rsub);
        return root;
        
    }
}

利用ArrayList的sublist方法时需要考虑下标的溢出问题，容易出错，我们可以给辅助函数多传几个参数，帮助提升辅助函数的作用以及使代码更加简化，数组越界的情况就比较好控制了，代码如下：

/**
 * 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 helper(0, 0, inorder.length - 1, preorder, inorder);
    }

    public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
        if (preStart > preorder.length - 1 || inStart > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preStart]);
        int inIndex = 0; // Index of current root in inorder
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == root.val) {
                inIndex = i;
            }
        }
        root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
        root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
        return root;
    }
}