Problem
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
Solution
常规思路
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
|
class { public: TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) { if (vin.size() <= 0 || pre.size() <= 0) { return NULL; }
TreeNode* root = new TreeNode(pre[0]);
vector<int> leftPre, leftVin, rightPre, rightVin;
bool isRootLeft = true;
for (int i = 0; i < vin.size(); ++i) { if(vin[i] == pre[0]) { isRootLeft = false; continue; }
if(isRootLeft) { leftVin.push_back(vin[i]); leftPre.push_back(pre[i+1]); } else { rightVin.push_back(vin[i]); rightPre.push_back(pre[i]); } }
root->left = reConstructBinaryTree(leftPre, leftVin); root->right = reConstructBinaryTree(rightPre, rightVin);
return root; } };
|
近期评论