6
要求
時間限制：1秒 空間限制：32768K
題目描述
輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹，假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字，例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并回傳
解題思路
解題的前提：兩個序列中必須有一個中序序列
前（后）序序列用于提供根節點，根節點就是序列第一個元素（最后一個元素）
中序序列用于確定當前根節點的左右子樹有哪些節點
如下圖所示：
確定了左右子樹有哪些元素之后就繼續遞回
代碼
/*
Definition for binary tree
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
*/
class Solution
{
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin)
{
int psize=pre.size();
int vsize=vin.size();
if(psize==0 || vsize==0 || psize != vsize)
return NULL;
return reBuildBinaryTreeCore(pre, 0, psize-1, vin, 0, vsize-1);
}
TreeNode* reBuildBinaryTreeCore(vector<int>& pre, int startIdxOfP, int endIdxOfP,
vector<int>& vin, int startIdxOfV, int endIdxOfV)
{
int valOfRoot = pre[startIdxOfP];
TreeNode* root = new TreeNode(valOfRoot);
if(startIdxOfP == endIdxOfP)
{
if(startIdxOfV == endIdxOfV)
return root;
else
{
cout << "無效輸入" << endl;
abort();
}
}
else
{
int idxOfRootInV = 0;
for(idxOfRootInV = startIdxOfV;idxOfRootInV <= endIdxOfV &&
vin[idxOfRootInV] != valOfRoot;++idxOfRootInV)
{
}
if(vin[idxOfRootInV] != valOfRoot)
{
cout << "無效輸入" << endl;
abort();
}
int leftLength = idxOfRootInV - startIdxOfV;
//左
if(startIdxOfV <= idxOfRootInV - 1)
root->left = reBuildBinaryTreeCore(pre,
startIdxOfP + 1,
startIdxOfP + leftLength,
vin,
startIdxOfV,
idxOfRootInV - 1);
//右
if(idxOfRootInV + 1 <= endIdxOfV)
root->right = reBuildBinaryTreeCore(pre,
startIdxOfP + 1 + leftLength,
endIdxOfP,
vin,
idxOfRootInV+1,
endIdxOfV);
}
return root;
}
};
由于還要搬磚，沒有辦法一一回復私信把學習資料發給大家，我直接整理出來放在下面，覺得有幫助的話可以下載下來用于學習
鏈接：https://pan.baidu.com/s/1C-9TE9ES9xrySqW7PfpjyQ 提取碼：cqmd
感謝各位人才的點贊、收藏、關注
微信搜「三年游戲人」識訓一枚有情懷的游戲人，第一時間閱讀最新內容，獲取優質作業內推
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/526855.html
標籤：其他
上一篇：資料結構(一):(順序表)設計演算法洗掉所有數字字符
下一篇：NGINX信號管理