LeetCode 剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下图：

0 <= 节点个数 <= 5000
做着一道题其实就是想学习一下二叉树的生成，以及二叉树的遍历方式，这里是通过前序遍历和中序遍历唯一确定一棵二叉树的，中序跟后序也是可以唯一确定一棵二叉树。只需要根据中序遍历和前序遍历之间的关系就可以生成一棵二叉树了。
前序遍历：根节点->左节点->右节点
中序遍历：左节点->跟节点->右节点
后序遍历：左节点->右节点->跟节点
是什么序遍历也就是看根节点遍历的位置
解决这个题的思路有两种，一种是递归，一种是迭代，感觉递归没那么麻烦，写好一种通用的处理，一直递归调用就好了。迭代是通过维护了一个栈实现。然后因为我用的是递归，我就说一下递归的思路吧
首先是根据前序遍历数组找到根节点的值，并创建一个根节点，再通过中序遍历搜索到根节点值在中序数组中的位置，该位置之前的全是根节点左子树的，之后的全是根节点右子树的，这样可以得到左子树的节点数量，根据这个值，可以得到左子树的前序遍历和中序遍历数组，还可以得到右子树的前序遍历和中序遍历数组，这样又把左子树看做一个完整的树，把右子树看做一个完整的树，递归调用该函数，需要注意的是返回的值是一个树节点，包括值val，左节点left，右节点right，因为左节点和右节点也是一个数节点，所以直接将递归返回的节点赋值给left和right就行了，还有就是结束递归的条件，我在这里提交错了一次，要特判只剩一个值和0个值(也就是没有值)的时候，只剩一个值直接返回该值的树节点就行，剩0个时直接返回null就结束了
贴出代码：

class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;
    function __construct($value) { $this->val = $value; }
}
class Solution {

    /**
     * @param Integer[] $preorder
     * @param [type] $[name] [description] Integer[] $inorder
     * @return TreeNode
     */
    function buildTree($preorder, $inorder) {
    	//当只剩最后一个值时，以该数组中的值作为节点返回
    	if (count($preorder) == 1) {
    		return new TreeNode($preorder[0]);
    	}
    	if (count($preorder) == 0) {
    		return null;
    	}
    	//根据前序遍历获取到根节点
    	$root = new TreeNode($preorder[0]);
    	$index = array_search($root->val, $inorder);
    	//左节点的数量
    	$left_num = $index;
    	//把左边和右边分开
    	$pre_left = array_slice($preorder, 1, $left_num);
    	$in_left = array_slice($inorder, 0, $left_num);
    	$pre_right = array_slice($preorder, $left_num+1);
    	$in_right = array_slice($inorder, $left_num+1);
    	//添加左节点和右节点
    	$root->left = $this->buildTree($pre_left, $in_left);
    	$root->right = $this->buildTree($pre_right, $in_right);
    	return $root;
    }
}