题解 | 重建二叉树

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param preOrder int整型vector 
     * @param vinOrder int整型vector 
     * @return TreeNode类
     */
    
    TreeNode* newOne(vector<int>& preOrder, vector<int>& vinOrder, int p1, int p2, int p3, int p4){
        
        TreeNode* cur = new TreeNode(preOrder[p1]);
        int preM, vinM;
        for(int i = p3; i <= p4; ++i){
            if(vinOrder[i]==preOrder[p1]){
                vinM = i;
                break;
            }
        }
        if(vinM!=p3) cur->left = newOne(preOrder, vinOrder, p1+1, p1+vinM-p3, p3, vinM-1);
        else cur->left = nullptr;
        if(vinM!=p4) cur->right = newOne(preOrder, vinOrder, p1+vinM-p3+1, p2, vinM+1, p4);
        else cur->right = nullptr;
        return cur;
    }
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        // write code here
        if(preOrder.empty()||vinOrder.empty()) return nullptr;
        return newOne(preOrder, vinOrder, 0, preOrder.size()-1, 0, vinOrder.size()-1);
    }
};

前序中序，中序后序都能唯一确定一棵树，注意如果需要比较B树是否是A树的子树并不能用这种方法，比如B树可以没有左子树但是A树对应的B树相应位置有左子树，也就是说B树作为子树缺的位置有多种情况。

回到这道题，前序中序问题，先找到前序的第一个节点，这个节点是中点，在中序数组中将中序数组分为左右两棵子树。

因此我们可以通过遍历中序数组查找该中点的方法把中序数组分为左子树、中点、右子树（顺序也是这个）三个部分。

因为在前序和中序序列中，同一子树的节点总是紧挨着，所以从上一步找出的左右子树长度可以对应划分前序序列，左子树在前右子树在后。

然后分别递归左右子树，这样循环往复，因为我们需要左右子树根节点作为当前根节点的左右节点，所以这个递归应该是后序访问的模式。

官方题解是直接传vector数组，逻辑对初学者来说更直观，我习惯使用下标，因为这样没有额外的数组生成。

为了避免悬空指针问题，在构造函数中如果没有初始化左右指针为空指针，有我代码中的else还是很有必要的。

或者更常用的是在函数中写一个退出机制，这里比如p3>=p4就返回空指针。

只是我个人觉得思考退出机制更容易忽略边界条件，在可以在外部不进入递归的情况下，我总是不愿意进入递归。