描述：
輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹，假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字，例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并回傳，
示例1
輸入：
[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
回傳值：
{1,2,5,3,4,6,7}
(題目來自牛客網)
用C++實作如下
/**
* //定義二叉樹的結構，包括val，TreeNode* left和TreeNode* right
* 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) {
//思路,輸入某二叉樹的前序遍歷和中序遍歷結果,重建改二叉樹
//前序遍歷為 根 左(全部) 右(全部)
//中序遍歷為 左(全部) 根 右(全部)
//前序和后序可以實作父子節點的分離,配合中序遍歷,可以確定一棵樹(前提是不含有重復的val值)
//方法,使用遞回演算法進行求解
return rebuild(pre, 0, pre.size()-1, vin, 0, vin.size()-1); //使用rebuild遞回函式進行求解;
}
TreeNode* rebuild(vector<int>& pre, int pre_left, int pre_right,
vector<int>& vin, int vin_left, int vin_right){
if(pre_left > pre_right) //size等于0,表示為空,vin與之對應著
return nullptr;
TreeNode* root = new TreeNode(pre[pre_left]); //建立根節點,前序遍歷第一個為根節點,括號中放val值;
for(int i = vin_left; i<=vin_right; i++) //遍歷中序,直到找到根節點的val;(由于不重復)
{
if(vin[i] == pre[pre_left]) //碰到了根節點;
{
root->left = rebuild(pre, pre_left+1, pre_left+i-vin_left, vin, vin_left, i-1);
//由于是根據中序進行遍歷的,根據for回圈可以知道,i-vin_left可以表示根節點左邊有多少個元素
root->right = rebuild(pre, pre_left+i-vin_left+1, pre_right, vin, i+1, vin_right);
break;
}
}
return root; //回傳值
}
};
純手撕代碼，如果覺得內容不錯麻煩點個贊，后面陸續配上Top100演算法題通俗易懂的講解視頻，可以花兩個月時間完全掌握，進大廠不是夢，轉行狗親測！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/287706.html
標籤：其他
上一篇：LeetCode 658 找到K個最接近的元素[二分法] HERODING的LeetCode之路
下一篇：陣列的基本知識及練習題