题解 | #重建二叉树#

重建二叉树

http://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6

1 提交总结

边界case 耗时累计2天！！
递归的入口参数容易错
递归的出口非常容易错
算法层面，还存在分治的思想。个人认为
可以尝试全局变量传参，减少内存占用

1.1 向量只有一个的大小判定

alt

1.2 关于找不到索引的超4行代码，待优化处理

alt

1.3 递归的边界

alt

1.4 leetcode cn扩展

一棵二叉树能够被重建，如果满足下面三个条件之一：

　　　　a1. 已知先序遍历；或
　　　　a2. 已知后序遍历；或
　　　　a3. 【扩展】已知层序遍历；

且满足下面三个条件之一：

b1. 前面已知的那种遍历包含了空指针；或
b2. 【注意】已知中序遍历，且树中不含重复元素；或
b3. 树是二叉搜索树，且不含重复元素。

链接

1.4.1 图片解释

alt

1.4.2 题解889

url

每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。题目中说过了，会有多种答案

2 code

涵盖vector引用版本
vector全局变量版本
含有精简STL版本
todo pre后边界删除版本

最关键就是边界的处理，递归的出口


/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
//global one 
using namespace std;
std::vector<int> pre2 ;
std::vector<int> vin2 ;

//https://www.runoob.com/w3cnote/cpp-vector-container-analysis.html
/*
vector<int> temlist;
temlist.assign(list.begin(), list.end());
*/

class Solution {
public:

//pre end参数可以省略
TreeNode * rebuild(int pre_start, int pre_end , int in_start, int in_end ) 
{//check null

/*         if(pre2.size()==0 || vin2.size()==0 || pre2.size() !=vin2.size()){
                return NULL;
        } */
        int inDiff = in_start - in_end , preDiff = pre_start - pre_end;
        if(in_start > in_end || pre_start > pre_end || inDiff!=preDiff ){
            return NULL;
        }
    
            //pay atttention to start
        TreeNode * root = new TreeNode(pre2[pre_start]);
        //root->left = NULL;
        //root->right = NULL;

        //只有一个节点
        if( in_end - in_start == 0){
            return root;
        }

        //先序第一个在中序的位置
        // Check if element 22 exists in vector
        //std::vector<int>::iterator it = std::find(vecOfNums.begin(), vecOfNums.end(), 22);
        //size not length

        int index = 0;
        bool isFound = false;
        //pay atttention to start, in start
        //for(int i= in_start; i< vin2.size(); i++){
		for(int i= in_start; i<= in_end ; i++){
                if(pre2[pre_start] == vin2[i]){
                        index = i;
                        isFound = true;
                        break;//添加break
                }
                        
        }
		
		if(!isFound ){//不止一个节点
		return NULL;
        //return root;
		}
		//exit 2
		//不含Index，所以不用 + 1//66补充
        int len = index - in_start ;
    
        //if( len == 0){
        //if( len <= 1){
        //    return root;
        //}
        root->left = rebuild( pre_start+1  ,  pre_start + len , in_start ,  index -1);
        root->right = rebuild( pre_start + len+1   , pre_end, index+1 , in_end );

        return root;
}
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {

        //check null
        if(pre.size()==0 || vin.size()==0){
                return NULL;
        }

        pre2 = pre;
        vin2 = vin;
        //pre2.assign(pre.begin(),pre.end());
        //vin2.assign(vin.begin(),vin.end());

        int allLen = pre.size();
        return rebuild(0,allLen-1 ,0,allLen-1  );

    }
};

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
//global one 
using namespace std;
//std::vector<int> pre2 ;
//std::vector<int> vin2 ;

//https://www.runoob.com/w3cnote/cpp-vector-container-analysis.html
/*
vector<int> temlist;
temlist.assign(list.begin(), list.end());
*/
class Solution {
public:

//pre end参数可以省略
TreeNode * rebuild(int pre_start, int pre_end , int in_start, int in_end ,vector<int> & pre2,vector<int> & vin2) 
{//check null
        if(pre2.size()==0 || vin2.size()==0 || pre2.size() !=vin2.size()){
                return NULL;
        }
    
            //pay atttention to start
        TreeNode * root = new TreeNode(pre2[pre_start]);
        if(pre2.size() ==1 ){
            return root;
        }
        //先序第一个在中序的位置
        // Check if element 22 exists in vector
        //std::vector<int>::iterator it = std::find(vecOfNums.begin(), vecOfNums.end(), 22);
        //size not length

        int index = 0;
        bool isFound = false;
        //pay atttention to start, in start
        //for(int i= in_start; i< vin2.size(); i++){
		for(int i= in_start; i<= in_end ; i++){
                if(pre2[pre_start] == vin2[i]){
                        index = i;
                        isFound = true;
                        break;//添加break
                }
                        
        }
		
		if(!isFound ){//不止一个节点
		return NULL;
		}
		
		//exit 2
		//不含Index，所以不用 + 1//66补充
        int len = index - in_start ;



        root->left = rebuild( pre_start+1  ,  pre_start + len , in_start ,  index -1 ,pre2,vin2);
        root->right = rebuild( pre_start + len+1   , pre_end, index+1 , in_end  ,pre2,vin2 );

        return root;
}
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {

        //check null
        if(pre.size()==0 || vin.size()==0){
                return NULL;
        }

        //pre2 = pre;
        //vin2 = vin;
        //pre2.assign(pre.begin(),pre.end());
        //vin2.assign(vin.begin(),vin.end());

        int allLen = pre.size();
        return rebuild(0,allLen-1 ,0,allLen-1  ,pre,vin );

    }
};

//https://blog.nowcoder.net/n/735ed60a9ea44be3ac3a6f13781cba91
/**
 * 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<int> pre,vector<int> vin) {
        if(pre.size() == 0 || pre.size() != vin.size())
            return nullptr;
        int root = pre[0];//树的第一个值为pre的第一个元素
        TreeNode *node = new TreeNode(root);
        //如果只剩一个节点了，那么可以直接返回
        if (pre.size() == 1)
            return node;
        auto posi = find(vin.begin(), vin.end(), root);
        //检测如果出现错误
        if (posi == vin.end()) {
            return nullptr;
        }
        int leftSize = posi - vin.begin();
        int rightSize = vin.end() - posi - 1;
        //递归求解
        node->left = reConstructBinaryTree(vector<int>(pre.begin() + 1, pre.begin() + 1 + leftSize),
        vector<int>(vin.begin(), vin.begin() + leftSize));
        node->right = reConstructBinaryTree(vector<int>(pre.begin() + 1 + leftSize, pre.end()),
        vector<int>(vin.begin() + leftSize + 1, vin.end()));
    return node;
    }
};

全部评论

推荐最新楼层

有pp才有真相

楼主

成都体育学院 Java

难在 rebuild 的递归（刷新输入root left and right），其中如果确定了前序第一个素，剩下元素群的划分【】很重要其他类型扩展一棵二叉树能够被重建，如果满足下面三个条件之一：　　　　a1. 已知先序遍历；或　　　　a2. 已知后序遍历；或　　　　a3. 【扩展】已知层序遍历；且满足下面三个条件之一： b1. 前面已知的那种遍历包含了空指针；或 b2. 【注意】已知中序遍历，且树中不含重复元素；或 b3. 树是二叉搜索树，且不含重复元素。

点赞回复分享

发布于 2022-11-22 12:02 四川