105.md

✏️Leetcode基础刷题之(105. Construct Binary Tree from Preorder)

2020-1-2 吴亲库里 库里的深夜食堂

---

✏️描述

给定二叉树的前序遍历和中序遍历，构建出这个二叉树。题目还有一个很好的前提是假设没有重复的值。

---

✏️题目实例

​

✏️题目分析

二叉树的遍历不了解的可以先行了解。从这两个遍历我们可以得到的信息是，从前序遍历我们可以知道根节点，知道了根节点我们就可以从中序遍历中知道左右子树。根据中序遍历根节点的位置反过来可以在前序遍历中确定左右子树分割的位置，可以分割左右子树，构建树。看到 Leetcode 国外一个大佬被围观的代码，不得不说，思路巧妙。

 
/**
     * @param Integer[] $preorder
     * @param Integer[] $inorder
     * @return TreeNode
     */
    function buildTree($preorder, $inorder)
{
        return $this->helper($preorder, 0, count($preorder) - 1, 
        $inorder, 0, count($inorder) - 1);
    }

    function helper(&$preorder, $pleft, $pright, &$inorder, $ileft, $iright)
{
        if ($pleft > $pright || $ileft > $iright) return null;

        $i = 0;

        for ($i = $ileft; $i <= $iright; $i++) {
            if ($preorder[$pleft] == $inorder[$i]) break;
        }

        $node = new TreeNode($preorder[$pleft]);
        $node->left = $this->helper($preorder, $pleft + 1, 
        $pleft + $i - $ileft, $inorder, $ileft, $i - 1);
        
        $node->right = $this->helper($preorder, $pleft + $i - $ileft + 1, 
        $pright, $inorder, $i + 1, $iright);
        return $node;
    }

---

如果觉得难理解，可以看看下面举的例子的过程。

​

联系

​