重建二叉树

重建普通二叉树

• 优化，借助下标索引，而不是vector；
• 不能从前序和后序重建；
• 左闭右开（或左闭右闭）就是循环不变量；

一、从中序和后序重建

①传vector

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        //保证输入合规、节点值唯一
        return build(inorder, postorder);
    }
private:
    TreeNode* build(vector<int>& inorder, vector<int>& postorder) {
        //第一步：如果为空，返回
        int n = postorder.size();
        if(!n) return nullptr;

        //第二步：从后序最后一个得到根节点
        int rootValue = postorder[n-1];
        TreeNode* root = new TreeNode(rootValue);

        //叶子节点
        if(1 == n) return root;

        //第三部：根据根节点切分中序，得到 中序左序列（左子树）、中序右序列（右子树）
        int cutIndex1 = 0;
        for(; cutIndex1 < n; ++cutIndex1){
            if(inorder[cutIndex1] == rootValue){
                break;
            }
        }
        // 左闭右开区间：[0, cutIndex)
        vector<int> inorderLeft(inorder.begin(), inorder.begin() + cutIndex1);
        // [cutIndex + 1, end)
        vector<int> inorderRight(inorder.begin() + cutIndex1 + 1, inorder.end());

        //第四步：根据左右子树切分后序序列得到 后序左序列（左子树）、后序右序列（右子树）
        // 先postorder舍弃末尾元素，因为这个元素就是中间根节点，已经用过了
        postorder.resize(n - 1);
        int cutIndex2 = inorderLeft.size();//使用了左中序数组大小作为切割点
        // 左闭右开，[0, inorderLeft.size())
        vector<int> postorderLeft(postorder.begin(), postorder.begin() + cutIndex2);
        // [inorderLeft.size(), end)
        vector<int> postorderRight(postorder.begin() + cutIndex2, postorder.end());

        //第五步：递归处理左右区间
        root->left = build(inorderLeft, postorderLeft);
        root->right = build(inorderRight, postorderRight);
        return root;
    }
};

②传index

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = inorder.size();
        return build(inorder, postorder, 0, n - 1, 0, n - 1);
    }
private:
    TreeNode* build(vector<int>& inorder, vector<int>& postorder, int inStart, int inEnd,
    int postStart, int postEnd) {
        // 左闭右开
        if (inStart > inEnd) return nullptr;

        int rootValue = postorder[postEnd];
        TreeNode* root = new TreeNode(rootValue);

        int idx = inStart;
        for (int i = inStart; i <= inEnd; ++i) {
            if (inorder[i] == rootValue) {
                idx = i;
                break;
            }
        }

        int leftInStart = inStart;
        int leftInEnd = idx - 1;
        int leftPostStart = postStart;
        int leftPostEnd = postStart + leftInEnd - leftInStart;
        //printf("%d | %d %d %d %d\n", idx, leftInStart, leftInEnd, leftPostStart, leftPostEnd);
        TreeNode* left = build(inorder, postorder, leftInStart, leftInEnd, leftPostStart, leftPostEnd);

        int rightInStart = idx + 1;
        int rightInEnd = inEnd;
        int rightPostStart = leftPostEnd + 1;
        int rightPostEnd = postEnd - 1;
        TreeNode* right = build(inorder, postorder, rightInStart, rightInEnd, rightPostStart, rightPostEnd);

        root->left = left;
        root->right = right;

        return root;
    }
};

二、从中序和前序重建

①传vector

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder, inorder);
    }
    TreeNode* build(vector<int>& preorder, vector<int>& inorder) {
        //第一步：判断是否为空
        int n = inorder.size();
        if(!n) return nullptr;

        //第二步：从前序第一个找到根节点
        TreeNode* root = new TreeNode(preorder[0]);
        if(n == 1) return root;

        //第三步：切分中序
        int inorderCutIndex = 0;
        for(; inorderCutIndex < n; ++inorderCutIndex){
            if(inorder[inorderCutIndex] == preorder[0]){
                break;
            }
        }
        vector<int> inorderLeft(inorder.begin(), inorder.begin() + inorderCutIndex);
        vector<int> inorderRight(inorder.begin() + inorderCutIndex + 1, inorder.end());

        //第四步：切分前序
        int preorderCutIndex = inorderLeft.size() + 1;//加1是因为跳过第一个用过的根节点
        vector<int> preorderLeft(preorder.begin() + 1, 
                                 preorder.begin() + preorderCutIndex);
        vector<int> preorderRight(preorder.begin() + preorderCutIndex, preorder.end());

        //第五步：递归处理
        root->left = build(preorderLeft, inorderLeft);
        root->right = build(preorderRight, inorderRight);

        return root;
    }
};

②传index

class Solution {
private:
    TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, 
                         vector<int>& preorder, int preorderBegin, int preorderEnd) {
        if (preorderBegin == preorderEnd) return nullptr;

        int rootValue = preorder[preorderBegin]; // 注意用preorderBegin 不要用0
        TreeNode* root = new TreeNode(rootValue);
        if (preorderEnd - preorderBegin == 1) return root;

        // 切割中序数组
        int delimiterIndex = inorderBegin;
        for (; delimiterIndex < inorderEnd; delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }
        // 中序左区间，左闭右开[leftInorderBegin, leftInorderEnd)
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimiterIndex;
        // 中序右区间，左闭右开[rightInorderBegin, rightInorderEnd)
        int rightInorderBegin = delimiterIndex + 1;
        int rightInorderEnd = inorderEnd;

        // 切割前序数组，(delimiterIndex - inorderBegin)是中序左区间的大小
        // 前序左区间，左闭右开[leftPreorderBegin, leftPreorderEnd)
        int leftPreorderBegin =  preorderBegin + 1;
        int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin; 
        // 前序右区间, 左闭右开[rightPreorderBegin, rightPreorderEnd)
        int rightPreorderBegin = preorderBegin + 1 + delimiterIndex - inorderBegin;
        int rightPreorderEnd = preorderEnd;

        root->left = traversal(inorder, leftInorderBegin, leftInorderEnd, 
                               preorder, leftPreorderBegin, leftPreorderEnd);
        root->right = traversal(inorder, rightInorderBegin, rightInorderEnd,
                                preorder, rightPreorderBegin, rightPreorderEnd);

        return root;
    }

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 参数坚持左闭右开的原则
        return traversal(inorder, 0, inorder.size(), preorder, 0, preorder.size());
    }
};

重建平衡二叉树

• 从数组构造二叉树，构成平衡树是自然而然的事情；
• 寻找分割点，分割点作为当前节点，然后递归左区间和右区间；
• 分割点就是数组中间位置的节点；
• 从有序数组构建就是平衡二叉搜索树；
• 构造二叉树的时候尽量不要重新定义左右区间数组，而是用下标来操作原数组；
• 我们选择左闭右闭的区间作为循环不变量；

TreeNode* buildBST(vector<int>& nums, int left, int right){
    if(left > right) return nullptr;
    int mid = left + (right - left) / 2;
    TreeNode* root = new TreeNode(nums[mid]);
    root->left = buildBST(nums, left, mid - 1);
    root->right = buildBST(nums, mid + 1, right);
    return root;
}