一、题目描述
二、解题思路
我写过一篇从前序和中序遍历序列构造二叉树的文章，和这道题的思路是一模一样的
三、解题代码
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(!postorder.size() || !inorder.size()) return nullptr;
return MyCreate(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
}
private:
TreeNode* MyCreate(vector<int>& inorder, unsigned int in_l, unsigned int in_r, vector<int>& postorder, unsigned int pos_l, unsigned int pos_r) {
auto Cur_Head = new TreeNode(postorder[pos_r]);
unsigned int in_head;
for(in_head = in_l; inorder[in_head] != Cur_Head->val; in_head++);
auto LeftTreeLen = in_head - in_l;
auto RightTreeLen = in_r - in_head;
Cur_Head->left = LeftTreeLen ? MyCreate(inorder, in_l, in_head - 1, postorder, pos_l, pos_l + LeftTreeLen - 1) : nullptr;
Cur_Head->right = RightTreeLen ? MyCreate(inorder, in_head + 1, in_r, postorder, pos_r - RightTreeLen, pos_r - 1) : nullptr;
return Cur_Head;
}
};
四、测试数据
可以用这组来试试
[1,5,6,8,20,31,3,7,42,9,8,2]
[5,20,8,31,6,1,7,3,9,2,8,42]
[20,31,8,6,5,7,2,8,9,42,3,1]
[1,5,3,null,6,7,42,8,null,null,null,9,null,20,31,null,8,null,null,null,null,2]
京公网安备 11010502036488号