1.題目
輸入一棵二叉樹前序遍歷和中序遍歷的結果，請重建該二叉樹，
注意:
- 二叉樹中每個節點的值都互不相同；
- 輸入的前序遍歷和中序遍歷一定合法；
樣例
給定：
前序遍歷是：[3, 9, 20, 15, 7]
中序遍歷是：[9, 3, 15, 20, 7]
回傳：[3, 9, 20, null, null, 15, 7, null, null, null, null]
回傳的二叉樹如下所示：
3
/ \
9 20
/ \
15 7
這是題目地址，有興趣的可以做一下，
2.時間復雜度為O(nlogn)的解法
這個是自己做的，準確來說算是實踐了一下自己上資料結構課學到的知識吧，
2.1 思路
如果前序序列不為空，那么第一個數一定是樹的根，我們再從中序序列找到這個數所在的位置，左半部分就是根的左子樹，右半部分就是根的右子樹，我們可以把左子樹再當作一棵樹，適當縮小先序序列的范圍，第一個數就是這個左子樹的根，然后再在中序序列去尋找這個數，繼續劃分，依此類推，當序列只剩下一個數時，代表我們找到了葉子節點，就不需要再繼續劃分了，
道理很簡單，但是操作起來出了點問題，還是邊界問題，要親自實作一遍才知道自己哪里有問題，
自己的代碼也蠻復雜的，沒有用一些數記錄下標，直接將序列縮小進行遞回，如果是利用下標值，可以不需要這么復雜，（此處就不修改代碼了）
2.2 代碼
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void insertToTree(TreeNode* T, vector<int> preorder, vector<int> inorder) {
T->val = preorder[0];
//當此時陣列中只有一個數時，表示當前節點無左右孩子，為樹葉
if (inorder.size() == 1)
return;
int i = 0;
//尋找該數在中序陣列中的位置，左半部分為其左子樹，右半部分為其右子樹，
for (; i < inorder.size(); i++) {
if (inorder[i] == T->val)
break;
}
//此時位于中序陣列第一位，表明無左孩子
if (i == 0) {
T->left = NULL;
T->right = new TreeNode(0);
insertToTree(T->right, vector<int>(preorder.begin() + i + 1, preorder.end()), vector<int>(inorder.begin() + i + 1, inorder.end()));
}
//位于中序陣列最后一位，表明無右孩子
else if (i == inorder.size() - 1) {
T->right = NULL;
T->left = new TreeNode(0);
insertToTree(T->left, vector<int>(preorder.begin() + 1, preorder.begin() + i + 1), vector<int>(inorder.begin(), inorder.begin() + i));
}
//有左右孩子
else {
T->right = new TreeNode(0);
T->left = new TreeNode(0);
insertToTree(T->left, vector<int>(preorder.begin() + 1, preorder.begin() + i + 1), vector<int>(inorder.begin(), inorder.begin() + i));
insertToTree(T->right, vector<int>(preorder.begin() + i + 1, preorder.end()), vector<int>(inorder.begin() + i + 1, inorder.end()));
}
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
//如果是空序列，回傳空樹
if (inorder.size() == 0) return NULL;
TreeNode* T = new TreeNode(0);
insertToTree(T, preorder, inorder);
return T;
}
3.時間復雜度為O(n)的解法
這是題解，還是學的知識沒用上，忘記了散串列這么好用的東西，
大佬的題解的原地址
3.1 思路
思路和我自己想的是基本一樣的，只不過大佬在中序序列找數的這個程序中用的是散串列（學了一直沒用過，導致現在都不會用）
3.2 代碼
unordered_map<int,int> pos;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
for (int i = 0; i < n; i ++ )
pos[inorder[i]] = i;
return dfs(preorder, inorder, 0, n - 1, 0, n - 1);
}
TreeNode* dfs(vector<int>&pre, vector<int>&in, int pl, int pr, int il, int ir)
{
if (pl > pr) return NULL;
int k = pos[pre[pl]] - il;
TreeNode* root = new TreeNode(pre[pl]);
root->left = dfs(pre, in, pl + 1, pl + k, il, il + k - 1);
root->right = dfs(pre, in, pl + k + 1, pr, il + k + 1, ir);
return root;
}
作者：yxc
鏈接：https://www.acwing.com/solution/content/706/
來源：AcWing
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259931.html
標籤：其他