LeetCode刷题实战106：从中序与后序遍历序列构造二叉树
共 2257字，需浏览 5分钟
· 2020-11-26
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 从中序与后序遍历序列构造二叉树，我们先来看题面：
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
题意
解题
后序遍历：先左子树，后右子树，再根节点
class Solution {
public:
int orderSize;
vector<int> inorder;//类的属性，作用类似全局遍历
vector<int> postorder;
//inorder [inorderBegin, inorderEnd], postorder [postorderBegin, postorderEnd] 构造成一棵树
TreeNode* myBuildTree(int inorderBegin, int inorderEnd, int postorderBegin, int postorderEnd) {
TreeNode *root = NULL;
if (inorderBegin == inorderEnd) {
root = new TreeNode(inorder[inorderBegin]);
}
else if (inorderBegin < inorderEnd) {
root = new TreeNode(postorder[postorderEnd]);
int tempValue = postorder[postorderEnd];//根节点的值，因为postorder后序遍历最后访问的根节点
int rootIndex = inorderBegin;//根节点在inorder的下标
while (rootIndex < inorderEnd && inorder[rootIndex] != tempValue) {//寻找根节点在inorder的下标
++rootIndex;
}
int leftCnt = rootIndex - inorderBegin;//左子树的节点个数
root->left = myBuildTree(inorderBegin, rootIndex -1, postorderBegin, postorderBegin + leftCnt - 1);//构建左子树
root->right = myBuildTree(rootIndex + 1, inorderEnd, postorderBegin + leftCnt, postorderEnd - 1);//构建右子树
}
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
TreeNode* root = NULL;
orderSize = inorder.size();
int postorderSize = inorder.size();
if (orderSize == NULL || orderSize != postorderSize) {
return NULL;
}
this->inorder = inorder;//复制
this->postorder = postorder;
root = myBuildTree(0, orderSize - 1, 0, orderSize - 1);//构造
return root;
}
};
上期推文：