題目一：序列化和反序列化二叉樹

????題目：如圖8.3所示，請設計一個算法將二叉樹序列化成一個字符串，并能將該字符串反序列化出原來二叉樹的算法。
????這里考查的其實是二叉樹的創建和輸出，只需要固定使用前序、中序或者后序遍歷即可，比如構建二叉樹的時候使用前序遍歷，在進行反序列化的時候同樣使用前序遍歷的方式輸出。由于這里需要反序列化為字符串，使用#標識空節點，因此二叉樹的數據類型使用char類型。考慮到需要使用參數的形式去序列化構建一顆二叉樹，這里使用輸入的流的形式不太方便，分析發現可以使用一個隊列結構，將需要字符串讀入到隊列中，然后采用引用類型調用這個存儲了字符的隊列來構建二叉樹，這樣就能夠實現字符串序列化成一顆二叉樹，最終可以得到如下代碼：

treeNode* createTree(queue<char>& qu) {char val=qu.front();qu.pop();if(val=='#') {return nullptr;} else {treeNode* node=new treeNode(val);node->left=createTree(qu);node->right=createTree(qu);return node;}
}
treeNode* deserialize(string data) {queue<char> qu;for(int i=0,size=data.length(); i<size; ++i) {qu.push(data[i]);}return createTree(qu);
}
void serialize(treeNode* tree) {treeNode * p=tree;if(p==nullptr) {cout<<"#";return;} else {cout<<p->val;serialize(p->left);serialize(p->right);}
}

題目二：從根節點到葉節點的路徑數字之和

????題目：在一棵二叉樹中所有節點都在0～9的范圍之內，從根節點到葉節點的路徑表示一個數字。求二叉樹中所有路徑表示的數字之和。例如，圖8.4的二叉樹有3條從根節點到葉節點的路徑，它們分別表示數字395、391和302，這3個數字之和是1088。

????由于需要統計從根節點到葉子節點路徑數字和，那么需要拿到所有根節點到葉子節點的路徑。我們還能夠發現，這里可以考慮使用遞歸來簡化代碼邏輯，以395這條路徑為例，拿到3節點之后，相當于需要得到以9節點和0節點為根節點到葉子節點的和，這里存在一種數值關系，原根節點到葉子節點的和=上一級*10+下一級節點（新根節點）的路徑和。
????接下來，分析如何拿到根節點到葉子節點的所有路徑，從根節點向下一級節點探索，每次都需要探索左子節點和右子節點，這里立刻會想到前序遍歷，當前序遍歷拿到最后一個節點，即葉子節點，那么說明路徑完整了，這時候終止前面提到的上一級*10+下一級節點（新根節點）的路徑和這一遍歷過程。于是得到如下代碼：

int dfs(treeNode* tree,int path) {if(tree==nullptr) {return 0;}path=path*10+tree->val;if(!tree->left&&!tree->right) {return path;}return dfs(tree->left,path)+dfs(tree->right,path);
}int getAllPathSum(treeNode* tree) {return dfs(tree,0);
}

????這里的代碼將遞推關系和前序遍歷巧妙的結合起來，這里再回過頭捋一下思路，由于發現可以使用遞歸的形式計算下層根節點到葉子節點的值，因此可以整體上使用dfs(tree->left)+dfs(tree->right)的形式實現，遞歸的出口有兩個：
（1）一開始樹就為空，或者子樹左右兩邊中一邊為空；
（2）遞歸掃描到了葉子節點；
????為了保證每次path值都能帶入之后的計算，所以使用參數dfs傳參的方式向后傳遞，這里巧妙的是利用dfs(tree,0)開啟掃描，讓入口和接下來的遍歷遞推關系統一起來。

題目三：向下的路徑節點值之和

????題目：給定一棵二叉樹和一個值sum，求二叉樹中節點值之和等于sum的路徑的數目。路徑的定義為二叉樹中順著指向子節點的指針向下移動所經過的節點，但不一定從根節點開始，也不一定到葉節點結束。例如，在如圖8.5所示中的二叉樹中有兩條路徑的節點值之和等于8，其中，第1條路徑從節點5開始經過節點2到達節點1，第2條路徑從節點2開始到節點6。

????結合上一題的思路，這里同樣是需要使用先根節點、然后左孩子、右孩子的先序深度遍歷，區別在于這里的path值計算不一致，前面是用位數統計，這里只需要統計和。由于題意中描述說這里不僅僅需要考慮到跟到葉子節點的可能路徑數，還需要考慮到中間節點到其余節點的可能值，因此既需要考慮攜帶path向后遞歸，又需要考慮不攜帶path從新節點觸發的可能路徑數。還有一種情況需要考慮，在圖的深度優先遍歷時，我們常常需要考慮剪枝，這里由于沒有說明每個節點的數值是多少（沒有說每個節點的數值都是正數），因此不能提前找到路徑就終止遞歸。于是得到如下代碼：

void dfs(treeNode* tree,int path,int sum,int& count) {if(tree==nullptr) {return;}path=path+tree->val;if(path==sum) {count++;}if(!tree->left&&!tree->right) {return;}dfs(tree->left,path,sum,count);//攜帶傳值dfs(tree->right,path,sum,count);dfs(tree->left,0,sum,count);//不攜帶傳值dfs(tree->right,0,sum,count);
}

????這里可以得到一下總結，在使用遞歸的時候，需要明確如下幾點：
（1）遞歸入口以及進入遞歸的方式；
（2）遞歸出口；
（3）遞歸的遞推方式；
????對于統計可以視情況使用引用類型參數，比如這里巧妙的利用count引用類型實現統計所有路徑。

附錄：源碼gitee倉庫

????考慮到有些算法需要模擬數據，如果全部放進來代碼顯得過長，不利于聚焦在算法的核心思路上。于是把所有的代碼整理到了開源倉庫上，如果想要看詳細模擬數據，可在開源倉庫自取：【凌空暗羽/劍指Offer-C++版手寫代碼】。

????我是【Jerry說前后端】，本系列精心挑選的算法題目均基于經典的《劍指 Offer（數據結構與算法面試題精講）》。在如今競爭激烈的技術求職環境下，算法能力已成為前端開發崗位筆試考核的關鍵要點。通過深入鉆研這一系列算法題，大家能夠系統地積累算法知識和解題經驗。每一道題目的分析與解答過程，都像是一把鑰匙，為大家打開一扇通往高效編程思維的大門，幫助大家逐步提升自己在數據結構運用、算法設計與優化等方面的能力。
????無論是即將踏入職場的應屆畢業生，還是想要進一步提升自身技術水平的在職開發者，掌握扎實的算法知識都是提升競爭力的有力武器。希望大家能跟隨我的步伐，在這個系列中不斷學習、不斷進步，為即將到來的前端筆試做好充分準備，順利拿下心儀的工作機會！快來訂閱吧，讓我們一起開啟這段算法學習之旅！