72,73.Construct Binary Tree

72.Construct Binary Tree from Inorder and Postorder Traversal(Medium)

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

Notice

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

Example

Given inorder[1,2,3]and postorder[1,3,2], return a tree:

  2
 / \
1   3

Code

https://siddontang.gitbooks.io/leetcode-solution/content/tree/construct_binary_tree.html

要知道如何构建二叉树，首先我们需要知道二叉树的几种遍历方式，譬如有如下的二叉树：

                1
        --------|-------
        2               3
    ----|----       ----|----
    4       5       6       7

• 前序遍历 1245367

• 中序遍历 4251637

• 后续遍历 4526731

具体到上面这一题，我们知道了一个二叉树的中序遍历以及后序遍历的结果，那么如何构建这颗二叉树呢？

仍然以上面那棵二叉树为例，我们可以发现，对于后序遍历来说，最后一个元素一定是根节点，也就是1。然后我们在中序遍历的结果里面找到1所在的位置，那么它的左半部分就是其左子树，有半部分就是其右子树。

我们将中序遍历左半部分425取出，同时发现后序遍历的结果也在相应的位置上面，只是顺序稍微不一样，也就是452。我们可以发现，后序遍历中的2就是该子树的根节点。

上面说到了左子树，对于右子树，我们取出637，同时发现后序遍历中对应的数据偏移了一格，并且顺序也不一样，为673。而3就是这颗右子树的根节点。

重复上述过程，通过后续遍历找到根节点，然后在中序遍历数据中根据根节点拆分成两个部分，同时将对应的后序遍历的数据也拆分成两个部分，重复递归，就可以得到整个二叉树了。

这里我们需要注意，为了保证快速的在中序遍历结果里面找到根节点，我们使用了hash map。

public HashMap<Integer,Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder == null || postorder.length == 0 || inorder == null || inorder.length == 0 ) {
            return null;
        }
        map=new HashMap<Integer,Integer>();
        for (int i = 0; i < inorder.length; ++i){
            map.put(inorder[i],i);
        }

        int right1 = inorder.length-1;
        int right2 = postorder.length-1;
        return build(inorder,0,right1,postorder,0,right2);

    }

    public TreeNode build(int[] inorder, int left1, int right1,
                          int[] postorder, int left2, int right2) {
            if (left1 > right1 || left2 > right2){
                return null;
            } 
            TreeNode root = new TreeNode(postorder[right2]);

            //get the index of current root in inorder array
            //new inorder-->(left1,mid-1) && (mid+1,right1)
            int mid = map.get(postorder[right2]);
            //用num记录下次遍历的数组的长度，好计算left和right
            int num = mid-left1;

            //dfs: 注意上面的范围
            root.left = build(inorder, left1, mid-1, postorder, left2, left2+num-1);
            root.right = build(inorder, mid+1, right1, postorder, left2+num, right2-1);

            return root;
    }

73.Construct Binary Tree from Preorder and Inorder Traversal

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

Notice

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

Example

Given in-order[1,2,3]and pre-order[2,1,3], return a tree:

  2
 / \
1   3

Code

这题跟上面那题类似，通过前序遍历和中序遍历的结果构造二叉树，我们只需要知道前序遍历的第一个值就是根节点，那么仍然可以采用上面提到的方式处理：

• 通过前序遍历找到根节点

• 通过根节点将中序遍历数据拆分成两部分

• 对于各个部分重复上述操作

注意每次递归时index的计算

public HashMap<Integer,Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0){
            return null;
        }
        map = new HashMap<Integer,Integer>();
        for (int i = 0; i< inorder.length; ++i) {
            map.put(inorder[i],i);
        }
        int right1 = preorder.length-1;
        int right2 = inorder.length-1;

        return build(preorder, 0, right1, inorder, 0, right2);
    }

    public TreeNode build (int[] preorder, int left1, int right1,
                           int[] inorder, int left2, int right2) {
            if (left1 > right1 || left2 > right2 ){
                return null;
            } 
        TreeNode root = new TreeNode(preorder[left1]);

        int mid = map.get(preorder[left1]);
        int num = mid-left2;

        root.left = build(preorder, left1+1, left1+num, inorder, left2,mid-1);
        root.right = build(preorder, left1+num+1, right1, inorder, mid+1, right2);

        return root;
    }