How to reconstruct a binary tree in PHP based on the results of pre-order and in-order traversal (code)

The content of this article is about how PHP can reconstruct a binary tree (code) based on the results of pre-order and in-order traversal. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you. help.

Enter the results of pre-order traversal and in-order traversal of a binary tree, please reconstruct the binary tree. It is assumed that the results of the input pre-order traversal and in-order traversal do not contain repeated numbers. For example, if you input the pre-order traversal sequence {1,2,4,7,3,5,6,8} and the in-order traversal sequence {4,7,2,1,5,3,8,6}, then reconstruct the binary tree and return.
1. Pre-order traversal is center, left, right; mid-order traversal is left, center, right
2. The first node of pre-order traversal is the root node, and mid-order traversal of the array is from the beginning to the root. All the nodes are left subtrees. You can know the number of left subtrees. The right subtree to the right of the root node is the right subtree
3. Preorder traversal except the 0 position, from 1 to the number of left subtrees is The left subtree, the others are the right subtree
4. Determine four arrays, the preorder left subtree array, the preorder right subtree array, the inorder left subtree array, the inorder right subtree array; recursive call

reConstructBinaryTree(pre,in)
    if(pre.length) return null//递归终止条件
    root=pre[0]
    Node=new Node(root)
    //在中序中找根结点的位置
    p=0
    for p;p<pre.length;p++
        if in[p]==root break
    for i=0;i<pre.length;i++
        
        if i<p
            //中序左子树数组
            inLeft[]=in[i]
            //前序左子树数组
            preLeft[]=pre[i+1]
        else if i>p
            //中序的右子树
            inRight[]=in[i]
            //前序的右子树
            preRight[]=pre[i]
    Node->left=reConstructBinaryTree(preLeft,inLeft)
    Node->right=reConstructBinaryTree(preRight,inRight)
    return Node

<?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();
        $vinLeft=array();
        $vinRight=array();
        for($i=0;$i<$len;$i++){
                if($i<$p){
                        $preLeft[]=$pre[$i+1];
                        $vinLeft[]=$vin[$i];
                }else if($i>$p){
                        $preRight[]=$pre[$i];
                        $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
    }
  }
}

The above is the detailed content of How to reconstruct a binary tree in PHP based on the results of pre-order and in-order traversal (code). For more information, please follow other related articles on the PHP Chinese website!