本文共 2625 字，大约阅读时间需要 8 分钟。

如何根据前序和中序遍历重建二叉树

给定二叉树的前序遍历和中序遍历结果，可以通过递归的方法重建二叉树。以下是详细的步骤说明：

以下是用PHP实现的代码示例：

class TreeNode {    var $val;    var $left = NULL;    var $right = NULL;    function __construct($val) {        $this->val = $val;    }}function reConstructBinaryTree($pre, $vin) {    $len = count($pre);    if ($len == 0) {        return null;    }    $root = $pre[0];    $node = new TreeNode($root);    // 查找中序数组中根节点的位置    for ($p = 0; $p < $len; $p++) {        if ($vin[$p] == $root) {            break;        }    }    // 分割前序数组    $preLeft = array();    $preRight = array();    for ($i = 0; $i < $len; $i++) {        if ($i < $p) {            $preLeft[] = $pre[$i + 1];        } else if ($i > $p) {            $preRight[] = $pre[$i];        }    }    // 分割中序数组    $vinLeft = array();    $vinRight = array();    for ($i = 0; $i < $len; $i++) {        if ($i < $p) {            $vinLeft[] = $vin[$i];        } else if ($i > $p) {            $vinRight[] = $vin[$i];        }    }    // 递归构建左子树    $node->left = reConstructBinaryTree($preLeft, $vinLeft);    // 递归构建右子树    $node->right = reConstructBinaryTree($preRight, $vinRight);    return $node;}// 示例使用$pre = array(1, 2, 4, 7, 3, 5, 6, 8);$vin = array(4, 7, 2, 1, 5, 3, 8, 6);$node = reConstructBinaryTree($pre, $vin);var_dump($node);

输出结果：

object(TreeNode)#1 (3) {    ["val"]=>    int(1)    ["left"]=>    object(TreeNode)#2 (3) {        ["val"]=>        int(2)        ["left"]=>        object(TreeNode)#3 (3) {            ["val"]=>            int(4)            ["left"]=>            NULL            ["right"]=>            object(TreeNode)#4 (3) {                ["val"]=>                int(7)                ["left"]=>                NULL                ["right"]=>                NULL            }        }        ["right"]=>        NULL    }    ["right"]=>    object(TreeNode)#5 (3) {        ["val"]=>        int(3)        ["left"]=>        object(TreeNode)#6 (3) {            ["val"]=>            int(5)            ["left"]=>            NULL            ["right"]=>            NULL        }        ["right"]=>        object(TreeNode)#7 (3) {            ["val"]=>            int(6)            ["left"]=>            object(TreeNode)#8 (3) {                ["val"]=>                int(8)                ["left"]=>                NULL                ["right"]=>                NULL            }            ["right"]=>            NULL        }    }}

通过上述方法，可以成功地从前序和中序遍历结果中重建出对应的二叉树结构。