前序与中序遍历构造二叉树

通过刷题学习，现在对二叉树递归遍历有新的认识。

前序遍历：根节点，左子树，右子树

中序遍历：左子树，根节点，右子树

由此可见，前序遍历的第一个节点就是中序遍历的根节点

此处设前序遍历中，左子树的右边界为x，由于左子树结点的个数在前序和中序遍历中相同，即x -(pl+1)=(inroot-1) - il,故推出

x = inroot - il + pl，求出左子树右边界的下标。

求出边界值之后，找出根节点便能对棵子树按上面的顺序进行递归遍历。

另外，通过哈希表存储中序遍历的根节点（以前的方法是遍历中序序列，与前序结点比较，相同则为根结点，这样时间复杂度较高），通过哈希表映射能快速定位中序序列根节点的位置。只需用O(1)的时间。

class Solution {
    unordered_map<int,int>index;
public:
    TreeNode* build(vector<int>& preorder, vector<int>& inorder,int pl,int pr,int il,int ir){
        if(pl > pr)
            return nullptr;
        int pre_root = pl;
        int in_root = index[preorder[pre_root]]; //中序序列的根结点
        TreeNode* root = new TreeNode(preorder[pre_root]); //建立根结点
        root->left = build(preorder,inorder,pl+1,pl+in_root-il,il,in_root-1);
        root->right = build(preorder,inorder,pl+in_root-il+1,pr,in_root+1,ir);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
       int n = preorder.size();
        for (int i = 0; i < n; ++i) {
            index[inorder[i]] = i;
        }
        return build(preorder, inorder, 0, n - 1, 0, n - 1);
    }
};

FEATURED TAGS

FRIENDS