重建二叉树

题目来源：

题目描述

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

解题思路：

例如：

前序序列{1,2,4,7,3,5,6,8} = pre

中序序列{4,7,2,1,5,3,8,6} = in

根据当前前序序列的第一个结点确定根结点，为 1

找到 1 在中序遍历序列中的位置，为 in[3]

切割左右子树，则 in[3] 前面的为左子树， in[3] 后面的为右子树

则切割后的左子树前序序列为：{2,4,7}，切割后的左子树中序序列为：{4,7,2}；

切割后的右子树前序序列为：{3,5,6,8}，切割后的右子树中序序列为：{5,3,8,6}

对子树分别使用同样的方法分解

代码：

1. C++

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {
   public:    TreeNode* reConstructBinaryTree(vector
   
     pre,vector
    
      vin) {
           int len = vin.size();        if(len <= 0)            return NULL;        // 存储在前序遍历和中序遍历序列中的左右子树顺序        vector
     
       pre_left, pre_right;        vector
      
        vin_left, vin_right;        // 1. 创建根节点，即先序遍历的第一个结点        TreeNode *root = new TreeNode(pre[0]);        // 2. 在中序遍历中查找根节点, 下标存放在index中        int index = 0;        for(int i = 0; i < len; i++){
               if(vin[i] == pre[0]){
                   index = i;                break;            }        }        // 3. 中序遍历中根节点的左侧为左子树，右侧为右子树        //    根据 中序遍历左/右子树的数量 确定 左/右子树在先序遍历中的序列        for(int i = 0; i < index; i++){
               vin_left.push_back(vin[i]);            pre_left.push_back(pre[i+1]);        }        for(int i = index+1; i
       
        left = reConstructBinaryTree(pre_left, vin_left);        root->right = reConstructBinaryTree(pre_right, vin_right);                return root;    }};

2. 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) {
           int len = pre.length;        if(pre.length <= 0 || in.length <= 0)            return null;        TreeNode root = new TreeNode(pre[0]);        for(int i = 0; i < len; i++){
               if(in[i] == pre[0]){
                   //copyOfRange是左闭右开的                //左子树                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1), Arrays.copyOfRange(in,0,i));                // 右子树                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,len), Arrays.copyOfRange(in,i+1,len));                                break;            }        }        return root;    }}

关于Java中的Arrays.copyOfRange() 方法
要使用这个方法，首先要 import java.util.*;
Arrays.copyOfRange(T[ ] original,int from,int to)
将一个原始的数组original，从下标from开始复制，复制到上标to，生成一个新的数组。
注意这里包括下标from，不包括上标to 。

转载地址：http://drben.baihongyu.com/

你可能感兴趣的文章