重建二叉树

今天刷题的时候碰到这道二叉树的题，这是数据结构中的重点知识，但由于学了已经一年多了，很多东西已经遗忘，今天把它拾起来。

• • • 题目
    • 基础知识铺垫
    • 题解

题目

输入某二叉树的先序遍历和中序遍历的结果，请重建出该二叉树。假设输入的先序遍历和中序遍历的结果中都不含重复的数字。例如输入先序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

基础知识铺垫

拿到这道题的时候我只知道先序遍历，但忘记了中序遍历是什么意思。来温故一下。

先序遍历

我们所说的先序遍历的规则是，每到一个节点的访问都是按照以下顺序
1. 先访问根节点
2. 先序遍历左子树
3. 先序遍历右子树

例如

我们 A 节点的访问 顺序就是 A->B->C

这是一个常规二叉树

按照先序遍历的规则就应该是
A->B->D->G->H->C->E->F->I
B 这里的时候因为到了 B 节点，所以当以 B 节点为根节点，先序遍历，后面一样的道理

中序遍历

中序遍历的规则：

1. 中序遍历左子树
2. 访问根节点
3. 中序遍历右子树

中序和先序 就是根节点后面再访问的区别；

所以根据上面的规则

我们的访问顺序是 G->D->H->B->A->E->C->I->F
注意： I 是左子树

后序遍历

后序遍历的规则：

1. 后序遍历左子树
2. 中序遍历右子树
3. 访问根节点

访问顺序 G->H->D->B->E->I->F->C->A

这些基础知识知道了之后，我们来看一看我们这题的解法

题解

我们这题告诉我们两个二叉树的遍历方法，让我们去求这个二叉树。

题目已知：先序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}

由先序遍历的规则知：

根节点为 {1}

由中序遍历规则知：

左子树为 {4,7,2}
根节点为 {1}
右子树为{5,3,8,6}

我们在左子树和右子树重复刚才操作，
左子树： 中序遍历为{4，7，2} 先序为{2，4，7}
根节点为{2}
左子树为{4，7} 左子树先序为{4，7}中序为{4，7} 所以 {7} 是{4}的右子树

如右子树：中序遍历为{5,3,8,6} 先序遍历为 {3，5，6，8}
{3}为根节点
左子树{5}
右子树{6，8} ，其中其先序为{6，8} 中序为{8，6}说明该右子树的左节点为{8} 根节点为{6}；

得到的二叉树为

java 版

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.Arrays;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
      if (pre.length == 0) {
            return null;
        }

        TreeNode node = null;
        for (int i = 0; i < in.length; i++) {
            if (pre[0] == in[i]) {
                 node = new TreeNode(pre[0]);
                node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1),Arrays.copyOfRange(in, 0, i));
                node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length),
                        Arrays.copyOfRange(in, i + 1, in.length));
            }
        }
        return node;

}

php 版

<?php

/*class TreeNode{
    var $val;
    var $left = NULL;
    var $right = NULL;
    function __construct($val){
        $this->val = $val;
    }
}*/
function reConstructBinaryTree($pre, $vin)
{
   if(!count($pre)){
        return null;
    }
    $node = new TreeNode($pre[0]);
    $i = array_search($pre[0],$vin);
    $node->left = reConstructBinaryTree(array_slice($pre,1,$i),array_slice($vin,0,$i));
    $node->right = reConstructBinaryTree(array_slice($pre,$i+1),array_slice($vin,$i+1));

    return $node;

}

和上面我们讲的记录差不多都是靠递归。 虽然写了两种，但是思路都是一样的，权当是熟悉函数好了。哈哈

吐槽下，因为不知道Arrays.copyOfRange(pre, 1, i+1) 这个函数，我还百度了半天。

之前我觉得我找 php 的工作还是用php写代码比较好，但是有的时候 php 版的太简单了。 以后我就两种都写好了.