Login light

2020-05-22 18:04:32

/**
 * 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) {
        $treeRoot = new TreeNode(null);
        $this->loop($treeRoot, $preorder, $inorder);
        return $treeRoot;
    }
    function loop($tree, $preorder, $inorder){
        $tree->val = $preorder[0];
        if(1 >= count($preorder)){
            return $tree;
        }
        $leftLen = array_search($preorder[0], $inorder);
        // $rightLen = count($inorder) - $leftLen - 1;
        //中序遍历 左
        $inorderLeft = array_slice($inorder, 0, $leftLen);
        //前序遍历 左
        $preorderLeft = array_slice($preorder, 1, $leftLen);;
        //中序遍历 右
        $inorderRight = array_slice($inorder, $leftLen + 1);
        //前序遍历 右
        $preorderRight = array_slice($preorder, $leftLen + 1);
        if(!empty($preorderLeft)){
            $treeLeft = new TreeNode(null);
            $tree->left = $this->loop($treeLeft, $preorderLeft, $inorderLeft);
        }
        if(!empty($preorderRight)){
            $treeRight = new TreeNode(null);
            $tree->right = $this->loop($treeRight, $preorderRight, $inorderRight);
        }
        return $tree;
    }
}