题解 | #重建二叉树#day1

/**
 * 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* build(vector<int>& preOrder, int b1, int e1, vector<int>& inOrder, int b2, int e2){
        if(b1 > e1 || b2 > e2) return NULL;

        TreeNode* node = new TreeNode(preOrder[b1]);
        int mid = 0;
        for(int i = b2; i <= e2; i++){
            if(inOrder[i] == preOrder[b1]){
                mid  = i;
                break;
            }
        }
        node->left = build(preOrder, b1 + 1, b1 + mid - b2, inOrder, b2, mid - 1);
        node->right = build(preOrder, b1 + mid - b2 + 1, e1, inOrder, mid + 1, e2);
        return node;
    } 
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        // write code here
        return build(preOrder, 0, preOrder.size() - 1, vinOrder,0, vinOrder.size() - 1);
        
    }
};

思路：

二叉树的前序遍历确定根节点位置，中序遍历划分左右子树。

难点：

递归实现，递归的结束条件不要忘写。

递归参数中前序和中序的开始和结束的位置容易写错：

左子树=前序开始位置是当前位置的下一位，结束位置是开始位置+中序找到的长度，中序开始位置是中序开始原位置，结束位置是找到位置的前一个位置。

右子树=前序开始位置是左子树的结束位置下一位，结束位置是前序结束原位置，中序开始位置是找到位置的下一个位置，结束位置的中序结束原位置。