105. 从前序与中序遍历序列构造二叉树

题意：

解题思路：

思路：
递归(dfs)：O(n)：树中的每个节点遍历一次
1. 先利用前序遍历找根节点：前序遍历的第一个数，就是根节点的值；
2. 在中序遍历中找到根节点的位置 kk，则 kk 左边是左子树的中序遍历，右边是右子树的中序遍历；
3. 假设左子树的中序遍历的长度是 ll，则在前序遍历中，根节点后面的 ll 个数，是左子树的前序遍历，剩下的数是右子树的前序遍历；
4. 有了左右子树的前序遍历和中序遍历，我们可以先递归创建出左右子树，然后再创建根节点；

PHP代码实现：

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {
    /**
     * @param Integer[] $preorder
     * @param Integer[] $inorder
     * @return TreeNode
     */
    function buildTree($preorder, $inorder) {
        if (!$preorder) return null;
        $x = array_shift($preorder);
        $node = new TreeNode($x);
        $key = array_search($x, $inorder);
        $node->left = $this->buildTree(array_slice($preorder, 0, $key), array_slice($inorder, 0, $key));
        $node->right = $this->buildTree(array_slice($preorder, $key), array_slice($inorder, $key + 1));
        return $node;
    }
}

GO代码实现：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }
    rootVal := preorder[0]
    i := 0
    // 查找根节点位置
    for ; i < len(inorder); i++ {
        if rootVal == inorder[i] {
            break
        }
    }
    root := &TreeNode{Val: rootVal}
    root.Left = buildTree(preorder[1:i+1], inorder[:i])
    root.Right = buildTree(preorder[i+1:], inorder[i+1:])
    return root
}