NO IMAGE

題目描述

請實現一個函式,將一個字串中的空格替換成“%20”。例如,當字串為We Are Happy.則經過替換之後的字串為We%20Are%20Happy。

解題思路

輸入的是前序遍歷及中序遍歷的結果,如示例:
前序 : 1 2 4 7 3 5 6 8
中序 : 4 7 2 1 5 3 8 6

前序遍歷的第一個數肯定為root,然後分別構建它的左右子樹
在中序遍歷裡找到它的前一個數,若無,則左子樹為NULL;
若有,則構建左子樹;再找到它的後一個數,
若無,則右子樹為NULL;若有,則構建右子樹;
然後以root所在中序遍歷陣列位置分割成兩半,記錄前一半,
即左子樹的大小,然後在前序遍歷中也把左子樹和右子樹的子串
提出來,分別作為兩棵樹,重建,直到提出來的子串長度為0.
        1
    2      3
  4      5    6
    7         8

程式碼實現

class Solution7 {
public:
struct TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> in) {
return rebulidBinaryTree(pre, in);
}
static TreeNode* rebulidBinaryTree(vector<int>pre, vector<int>in){
if (pre.size() == 0 || in.size() == 0){
return NULL;
}
//獲取根節點
TreeNode* root = new TreeNode(pre[0]);
//查詢根節點在中序遍歷中的位置
int cur = -1;
for (int i = 0; i < in.size(); i  ){
if (pre[0] == in[i]){
cur = i;
break;
}
}
if (cur == -1){
return NULL;
}
//構建左子樹
vector<int> lin;
for (int i = 0; i < cur; i  ){
lin.push_back(in[i]);
}
vector<int> lpre;
for (int i = 1; i < lin.size()   1; i  ){
lpre.push_back(pre[i]);
}
root->left = rebulidBinaryTree(lpre, lin);
//構建右子樹
vector<int> rin;
for (int i = cur 1; i < in.size(); i  ){
rin.push_back(in[i]);
}
vector<int> rpre;
for (int i = 1 lin.size(); i < pre.size() ; i  ){
rpre.push_back(pre[i]);
}
root->right = rebulidBinaryTree(rpre, rin);
return root;
}
};