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;
    }
};