劍指 Offer 07. 重建二叉樹
輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建該二叉樹，假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字，
例如，給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]回傳如下的二叉樹：
3
/ \
9 20
/ \
15 7限制：
0 <= 節點個數 <= 5000
大概思路：
二叉樹的前序遍歷順序是：根節點、左子樹、右子樹，每個子樹的遍歷順序同樣滿足前序遍歷順序，二叉樹的中序遍歷順序是：左子樹、根節點、右子樹，每個子樹的遍歷順序同樣滿足中序遍歷順序，所以根據前序遍歷得知前面的就是跟節點，根據這個根節點在中序遍歷中就可以確定左子樹和右子樹，例如：3在preorder的第一個，那么他就是根節點，所以在中序遍歷inorder中[9]就是左子樹，[15,20,7]就是右子樹，層層遞回就能得到最終的二叉樹
代碼實作：
一，
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildTreeCode(vector<int>&preorder, int prestart, int preend, vector<int>& inorder, int inostart, int inoend)
{
if (prestart>preend || inostart > inoend)
{
return nullptr;
}
TreeNode *root = new TreeNode(preorder[prestart]);
for (auto i = inostart; i <= inoend; i++)
{
if (preorder[prestart] == inorder[i])
{
root->left = buildTreeCode(
preorder, prestart + 1, i - inostart + prestart,
inorder, inostart, i - 1);
//在前序排列中root就是prestart，所以prestart不在區間內
root->right = buildTreeCode(
preorder, i - inostart + prestart + 1, preend,
inorder, i + 1, inoend);
//在中序排列中第I個就是root所以在區間內不包括i
break;
}
}
return root;
}
TreeNode* buildTree(vector<int> &preorder, vector<int>&inorder) {
if (preorder.empty() || inorder.empty())
{
return nullptr;
}
return buildTreeCode(
preorder, 0, preorder.size() - 1,
inorder, 0, inorder.size() - 1);
}
};
注意：這個的取值空間的閉的，所以每次都將root節點都不在取值空間內，而且size()-1也是為了取到最后一個元素，保證是一個閉區間，
二，收到力扣題解的思路，在其中加入的迭代器，
class Solution {
public:
TreeNode* buildTreeCode(
vector<int>::iterator preBegin,
vector<int>::iterator preEnd,
vector<int>::iterator inBegin,
vector<int>::iterator inEnd)
{
if (inBegin == inEnd)
{
return nullptr;
}
TreeNode*cur = new TreeNode(*preBegin);
auto root = find(inBegin, inEnd, *preBegin);
cur->left = buildTreeCode(
preBegin + 1, preBegin + 1 + (root - inBegin),
inBegin, root);
//區間是左閉右開
cur->right = buildTreeCode(
preBegin + 1 + (root - inBegin), preEnd,
root + 1, inEnd);
return cur;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty() || inorder.empty())
{
return nullptr;
}
return buildTreeCode(preorder.begin(), preorder.end(),
inorder.begin(), inorder.end());
}
};注：迭代器end是指向性最后這個元素的下一個，所以這個的取值區間是左閉右開的，
這個題的最麻煩的就是確定取值區間，一定要先確定自己的取值區間是什么樣的，這樣帶遞回的時候才不會出錯
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/225392.html
標籤：其他