一、思路解析
1.简单的想法
题目要求是重建一颗二叉树，重建也是建立一颗二叉树。建立一颗二叉树就要从它的结构出发，把每个部分都填上值不就好了吗？
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
2.核心思路
- 创建一个节点。
- 给节点的val赋值
- 把它的左子树挂到left上
- 把它的右子树挂到right上
- 把左右子树挂上去之后节点就是一颗树了，把这棵树返回去就是答案。
那写代码试一试！！！
二、代码实现
1.核心代码
TreeNode *buildTree(/*参数列表*/){
if(/*节点不需要创建*/){
return nullptr;
}
/*1创建一个节点。2.给节点的val赋值*/
auto node = new TreeNode(val);
/*3.把它的左子树挂到left上*/
node->left = buildTree(/*参数列表*/);
/*4.把它的右子树挂到right上*/
node->right = buildTree(/*参数列表*/);
/*5. 把左右子树挂上去之后节点就是一颗树了，把这棵树返回去就是答案。*/
return node;
}
把我们的核心代码放进去就是这样的。
#include <vector>
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
TreeNode *root = buildTree(/*参数列表*/)；
return root;
}
TreeNode *buildTree(/*参数列表*/){
if(/*节点不需要创建*/){
return nullptr;
}
/*1创建一个节点。2.给节点的val赋值*/
auto node = new TreeNode(val);
/*3.把它的左子树挂到left上*/
node->left = buildTree(/*参数列表*/);
/*4.把它的右子树挂到right上*/
node->right = buildTree(/*参数列表*/);
/*5. 把左右子树挂上去之后节点就是一颗树了，把这棵树返回去就是答案。*/
return node;
}
};
2.核心代码的问题
这个代码运行制定是过不了的！
问题如下：
- 需要哪些参数
- 创建的node的val是多少
- 什么时候不需要创建新节点返回nullptr
简而言之，我们缺少这颗树的数据！
3.解决方案
参数与val
数据都在哪里？
数据在reConstructBinaryTree里
TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder){}
参数需要的内容就是：
- node的val在preOrder的什么位置？
- node的左右子树上的节点在vinOrder里面什么位置(或者说左子树的数据都在哪里、右子树的数据都在哪里)？
确定参数：
- preOrder——先序序列
- rootIndex——val在preOrder中的位置
- vinOrder——中序序列
- root_left——这颗树在vinOrder中范围的左边界
- root_right——这颗树在vinOrder中范围的右边界
完善核心代码
TreeNode *buildTree(
vector<int> &preOrder,//preOrder——先序序列
int rootIndex,//val在preOrder中的位置
vector<int> &vinOrder,//vinOrder——中序序列
int root_left,//root_left——这颗树在vinOrder中范围的左边界
int root_right//root_right——这颗树在vinOrder中范围的右边界
){
if(/*节点不需要创建*/){
return nullptr;
}
int val = preOrder[rootIndex];
auto node = new TreeNode(val);
int left_root_index;//左子树根节点的索引
int left_left;//左子树的在中序序列中的左边界
int left_right;//左子树的在中序序列中的右边界
int right_root_index;//右子树根节点的索引
int right_left;//右子树的在中序序列中的左边界
int right_right;//右子树的在中序序列中的右边界
node->left = buildTree(preOrder,left_root_Index,vinOrder,left_left,left_right);
node->right = buildTree(preOrder,right_root_Index,vinOrder,right_left,right_right);
return node;
}
我们知道
int val = preOrder[rootIndex];
那么rootIndex怎么确定呢？
我们先看一颗二叉树的结构：
按照遍历方法我们可以看到各个部分在先序遍历序列和中序遍历序列中的位置
也就是说在先序序列中，在这颗树的范围上第一个索引位置就是rootIndex
那整棵树的根节点的在先序遍历中的位置就是0.
整棵树在中序序列的范围就是整个中序序列。
完善代码：
TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
TreeNode* root = buildTree(preOrder, 0, vinOrder, 0, vinOrder.size() - 1);
return root;
}
解决不需要创建节点
当这棵树内没有一个节点的时候那肯定不需要创建了
那我怎么知道有没有节点了？
答：我们使用root_left和root_right标记这个树在中序序列内的范围，那在这个范围内没有数值的时候不就说明没有节点了吗？在就是要是rootIndex不在先序序列里面了不也就没有节点了吗？
if(rootIndex>=preOrder.size()||root_left>root_right){
return nullptr;
}
完善核心代码
TreeNode *buildTree(
vector<int> &preOrder,//preOrder——先序序列
int rootIndex,//val在preOrder中的位置
vector<int> &vinOrder,//vinOrder——中序序列
int root_left，//root_left——这颗树在vinOrder中范围的左边界
int root_right//root_right——这颗树在vinOrder中范围的右边界
){
/*不需要创建节点*/
if(rootIndex>=preOrder.size()||root_left>root_right){
return nullptr;
}
int val = preOrder[rootIndex];
auto node = new TreeNode(val);
int left_root_index;//左子树根节点的索引
int left_left;//左子树的在中序序列中的左边界
int left_right;//左子树的在中序序列中的右边界
int right_root_index;//右子树根节点的索引
int right_left;//右子树的在中序序列中的左边界
int right_right;//右子树的在中序序列中的右边界
node->left = buildTree(preOrder,left_root_Index,vinOrder,left_left,left_right);
node->right = buildTree(preOrder,right_root_Index,vinOrder,right_left,right_right);
return node;
}
子树的实参填写
在核心代码中许多参数的变量都是没有赋值的：
int left_root_index;//左子树根节点的索引 int left_left;//左子树的在中序序列中的左边界 int left_right;//左子树的在中序序列中的右边界 int right_root_index;//右子树根节点的索引 int right_left;//右子树的在中序序列中的左边界 int right_right;//右子树的在中序序列中的右边界
我们现在图上标记这颗树上我们知道的参数的位置：
然后再标记需要初始化的变量的位置：
我们发现有些变量和已知变量重合，而且左子树的根节点就是在rootIndex的下一个为他们初始化：
int left_root_index = rootIndex+1;//左子树根节点的索引 int left_left = root_left;//左子树的在中序序列中的左边界 int left_right;//左子树的在中序序列中的右边界 int right_root_index;//右子树根节点的索引 int right_left;//右子树的在中序序列中的左边界 int right_right = root_right;//右子树的在中序序列中的右边界
仔细看图片不难发现left_right和right_left在中序序列中的索引位置在绿色的根节点位置的一前一后，那只要知道这个绿色节点位置就可以得到这两个的值。
在vinOrder中找这preOrder[rootIndex]的索引位置
int mid;
for(int i = root_left;i <= root_right;i++){
if(vinOrder[i] == preOrder[rootIndex]){
mid = i;
break;
}
}
left_right = mid-1;
right_left = mid+1;
完善核心代码：
TreeNode *buildTree(
vector<int> &preOrder,//preOrder——先序序列
int rootIndex,//val在preOrder中的位置
vector<int> &vinOrder,//vinOrder——中序序列
int root_left，//root_left——这颗树在vinOrder中范围的左边界
int root_right//root_right——这颗树在vinOrder中范围的右边界
){
/*不需要创建节点*/
if(rootIndex>=preOrder.size()||root_left>root_right){
return nullptr;
}
int val = preOrder[rootIndex];
auto node = new TreeNode(val);
int mid;
for(int i = root_left;i <= root_right;i++){
if(vinOrder[i] == preOrder[rootIndex]){
mid = i;
break;
}
}
int left_root_index = rootIndex+1;//左子树根节点的索引
int left_left = root_left;//左子树的在中序序列中的左边界
int left_right = mid-1;//左子树的在中序序列中的右边界
int right_root_index;//右子树根节点的索引
int right_left = mid+1;;//右子树的在中序序列中的左边界
int right_right = root_right;//右子树的在中序序列中的右边界
node->left = buildTree(preOrder,left_root_Index,vinOrder,left_left,left_right);
node->right = buildTree(preOrder,right_root_Index,vinOrder,right_left,right_right);
return node;
}
现在只有
right_root_index
没有解决了。
再看这个图：
left_root_index已经知道了，那只要它加上蓝色块的长度就是right_root_index的位置。
求蓝色块的长度：
知道left_left和left_right，右边界减左边界加1就是长度
right_root_index = left_root_index + (left_right - left_left+1);
完善核心代码
TreeNode *buildTree(
vector<int> &preOrder,//preOrder——先序序列
int rootIndex,//val在preOrder中的位置
vector<int> &vinOrder,//vinOrder——中序序列
int root_left，//root_left——这颗树在vinOrder中范围的左边界
int root_right//root_right——这颗树在vinOrder中范围的右边界
){
/*不需要创建节点*/
if(rootIndex>=preOrder.size()||root_left>root_right){
return nullptr;
}
int val = preOrder[rootIndex];
auto node = new TreeNode(val);
int mid;
for(int i = root_left;i <= root_right;i++){
if(vinOrder[i] == preOrder[rootIndex]){
mid = i;
break;
}
}
int left_root_index = rootIndex+1;//左子树根节点的索引
int left_left = root_left;//左子树的在中序序列中的左边界
int left_right = mid-1;//左子树的在中序序列中的右边界
int right_root_index = left_root_index + (left_right - left_left + 1);//右子树根节点的索引
int right_left = mid+1;;//右子树的在中序序列中的左边界
int right_right = root_right;//右子树的在中序序列中的右边界
node->left = buildTree(preOrder,left_root_Index,vinOrder,left_left,left_right);
node->right = buildTree(preOrder,right_root_Index,vinOrder,right_left,right_right);
return node;
}
4.完整代码
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param preOrder int整型vector
* @param vinOrder int整型vector
* @return TreeNode类
*/
TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
TreeNode* root = buildTree(preOrder, 0, vinOrder, 0, vinOrder.size() - 1);
return root;
}
TreeNode* buildTree(
vector<int>& preOrder,//preOrder——先序序列
int rootIndex,//val在preOrder中的位置
vector<int>& vinOrder,//vinOrder——中序序列
int root_left,//root_left——这颗树在vinOrder中范围的左边界
int root_right//root_right——这颗树在vinOrder中范围的右边界
) {
/*不需要创建节点*/
if (rootIndex >= preOrder.size() || root_left > root_right) {
return nullptr;
}
int val = preOrder[rootIndex];
auto node = new TreeNode(val);
int mid;
for (int i = root_left; i <= root_right; i++) {
if (vinOrder[i] == preOrder[rootIndex]) {
mid = i;
break;
}
}
int left_root_index = rootIndex + 1; //左子树根节点的索引
int left_left = root_left;//左子树的在中序序列中的左边界
int left_right = mid - 1; //左子树的在中序序列中的右边界
int right_root_index = left_root_index + (left_right - left_left+1);//右子树根节点的索引
int right_left = mid + 1;; //右子树的在中序序列中的左边界
int right_right = root_right;//右子树的在中序序列中的右边界
node->left = buildTree(preOrder, left_root_index, vinOrder, left_left,
left_right);
node->right = buildTree(preOrder, right_root_index, vinOrder, right_left,
right_right);
return node;
}
};
京公网安备 11010502036488号