[Lc]面试题07重建二叉树

题目

注意：本题与主站 105 题重复：(https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)

题解

二叉树结构如下：

//Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

递归，先序的首字母是根节点，而中序的根节点区分左右子树，利用这个性质递归

时间复杂度$O(n)$,对于每个节点都有创建过程以及根据左右子树重建过程。
空间复杂度$O(n)$，存储整课树

class Solution {//递归
public:
    TreeNode* build(vector<int>& preorder, int pLeft, int pRight, vector<int>& inorder, int iLeft, int iRight){
        if(pLeft>pRight || iLeft>iRight) return nullptr;//若左右指针倒挂，返回空数组
        TreeNode* root = new TreeNode(preorder[pLeft]);//用先序遍历的首位建立根节点
        int i = iLeft;
        while(i<iRight && inorder[i] != preorder[pLeft])i++;//找到根节点在中序遍历中的位置
        int lLength = i-iLeft;
        int rLength = iRight-i;
        //计算左右子树的长度，不能直接用指向根节点的指针，因为后续递归可能前/中序遍历起点不同，应当计算出根节点相对于起点的偏移
        root->left = build(preorder, pLeft+1, pLeft+lLength, inorder, iLeft, iLeft+lLength);
        //递归求左子树，注意左子树起点，前序跳过首个数字，中序跳过根节点
        root->right = build(preorder, pLeft+lLength+1, pRight, inorder, iLeft+lLength+1, iRight);
        //右子树不用跳
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
    }
};

也可以用迭代，即用栈存数，有空再写，见官方题解

Contents

题目

题解