前往 中序, 后序遍历构造二叉树 https://www.cnblogs.com/brianyi/p/10803545.html , 中序, 前序遍历构造二叉树 https://www.cnblogs.com/brianyi/p/10803568.html
- TreeNode* build(vector<int>& inorder, int l1, int r1, vector<int>&postorder, int l2, int r2)
- {
- if (l1>r1) return nullptr;
- int x = postorder[r2], i = 0; // 确定当前根节点
- for (i = l1; i <= r1 && inorder[i] != x; ++i); // 在中序遍历序列中找到当前根节点位置 (该位置可以划分出左右两个分支)
- int llen = i - l1; // 左子树结点数量
- int rlen = r1 - i; // 右子树结点数量
- TreeNode* p = new TreeNode(x); // 建立根节点
- p->left = build(inorder, l1, l1 + llen - 1, postorder, l2, l2 + llen - 1); // 递归建立左子树,-1,-1 是把当前根节点位置去掉
- p->right = build(inorder, r1 - rlen + 1, r1, postorder, r2 - rlen, r2 - 1); // 递归建立右子树,+1,-1 是把当前根节点位置去掉
- return p;
- }
- TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
- if (inorder.empty()||postorder.empty()) return nullptr;
- return build(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
- }
来源: http://www.bubuko.com/infodetail-3044452.html