106. 从中序与后序遍历序列构造二叉树

题意：

解题思路：

思路：
递归(dfs)：创建每个节点需要的时间是 O(1)，所以总时间复杂度是 O(n)
1. 先利用后序遍历找根节点：后序遍历的最后一个数，就是根节点的值；
2. 在中序遍历中找到根节点的位置 k，则 k 左边是左子树的中序遍历，右边是右子树的中序遍历；
3. 假设左子树的中序遍历的长度是 l，则在后序遍历中，前 l 个数就是左子树的后序遍历，接下来的数除了最后一个，就是右子树的后序遍历；
4. 有了左右子树的后序遍历和中序遍历，我们可以先递归创建出左右子树，然后再创建根节点；

PHP代码实现：

class Solution {
    /**
     * @param Integer[] $inorder
     * @param Integer[] $postorder
     * @return TreeNode
     */
    function buildTree($inorder, $postorder) {
        if (!$postorder) return null;
        $x = array_pop($postorder);
        $node = new TreeNode($x);
        $key = array_search($x, $inorder);
        $node->left = $this->buildTree(array_slice($inorder, 0, $key), array_slice($postorder, 0, $key));
        $node->right = $this->buildTree(array_slice($inorder, $key + 1), array_slice($postorder, $key));
        return $node;
    }

GO代码实现：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(inorder []int, postorder []int) *TreeNode {
    length := len(postorder)
    if length == 0 {
        return nil
    }
    root := &TreeNode {
        Val: postorder[length-1],
    }
    index := 0
    for i, value := range inorder {
        if value == root.Val {
            index = i
            break
        }
    }
    root.Left = buildTree(inorder[:index], postorder[:index])
    root.Right = buildTree(inorder[index+1:], postorder[index:length-1])
    return root
}