前言

本文是基于代碼隨想錄上二叉樹章節的所有例題及其對應的算法思路（序號代表的是力扣題號）

為了避免很多讀者看不到最后 我寫在最前面 文章總字數預計超過25000字 制作不易 這些都是我在看了很多視頻之后整理而成的 希望先收藏點贊起來 以免后續丟失

算法思路主要參考（B站）：靈神 代碼隨想錄 labuladong 懶貓老師 想象力少年 在此跪謝！！！
所有題目講解視頻都可以在這里找到
視頻合集

不知道從哪入手的 參考我的學習順序：

• 1 懶貓老師的二叉樹章節視頻
• 2 labuladong二叉樹綱領篇
• 3 刷題配合著靈神和官方講解視頻

labuladong二叉樹綱領篇——遇到一道二叉樹的題目時的通用思考過程是：
1、是否可以通過遍歷一遍二叉樹得到答案？如果可以，用一個 traverse 函數配合外部變量來實現。
2、是否可以定義一個遞歸函數，通過子問題（子樹）的答案推導出原問題的答案？如果可以，寫出這個遞歸函數的定義，并充分利用這個函數的返回值。
3、無論使用哪一種思維模式，你都要明白二叉樹的每一個節點需要做什么，需要在什么時候（前中后序）做。

226.翻轉二叉樹

算法思路及代碼

solution 1 用分解問題的思路來解決

是我在沒看題解之前自己想出來的方法
我是怎么想的呢：
我們既然需要翻轉整顆二叉樹那么我們不妨先翻轉左子樹，在翻轉右子樹，然后將跟節點的左右子樹交換即可，這樣就好啦
遞歸的結束條件就是節點為空時結束

solution 2 用遍歷的思路來解決

這題我們只需要遍歷一遍二叉樹就可以解決問題，為什么這么說呢？
單獨抽出來一個結點來 我們只需要交換左右結點 對不對？ 而且我們需要在往下去遞歸之前做這件事情，也就是在前序位置去交換左右節點 然后其余的結點交給遞歸就好

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution 1 {
public:TreeNode* invertTree(TreeNode* root) {if(root==nullptr){return nullptr;}TreeNode* right= invertTree(root->left);TreeNode* left= invertTree(root->right);root->right=right;root->left=left;return root;}
};
class Solution 2 {
public:// 主函數TreeNode* invertTree(TreeNode* root) {// 遍歷二叉樹，交換每個節點的子節點traverse(root);return root;}// 二叉樹遍歷函數void traverse(TreeNode* root) {if (root == nullptr) {return;}// *** 前序位置 ***// 每一個節點需要做的事就是交換它的左右子節點TreeNode* tmp = root->left;root->left = root->right;root->right = tmp;// 遍歷框架，去遍歷左右子樹的節點traverse(root->left);traverse(root->right);}
};

101.對稱二叉樹

算法思路及代碼

對于這題 我們先不管代碼怎么實現，我們是不是同樣遍歷一遍二叉樹就可以把這個問題解決掉 我們只需要每往下遍歷以后 比較它的左右子樹即可（后序位置上）

solution

class Solution {
public:bool compare(TreeNode* left, TreeNode* right) {// 首先排除空節點的情況if (left == NULL && right != NULL) return false;else if (left != NULL && right == NULL) return false;else if (left == NULL && right == NULL) return true;// 排除了空節點，再排除數值不相同的情況else if (left->val != right->val) return false;// 此時就是：左右節點都不為空，且數值相同的情況// 此時才做遞歸，做下一層的判斷bool outside = compare(left->left, right->right);   // 左子樹：左、 右子樹：右bool inside = compare(left->right, right->left);    // 左子樹：右、 右子樹：左bool isSame = outside && inside;                    // 左子樹：中、 右子樹：中 （邏輯處理）return isSame;}bool isSymmetric(TreeNode* root) {if (root == NULL) return true;return compare(root->left, root->right);}
};

104.二叉樹的最大深度

算法思路及代碼

solution 1 遍歷

對于這道題目我們首先是不是同樣可以用遍歷的思路來解決，終止條件就是到達葉子節點，我們只需要一個traverse函數和一個外部變量來實現就行，在剛剛進入一個結點的時候（前序位置）去更新我們的maxdepth，在離開一個節點之前（后序位置）去維護depth。

class Solution {public:int depth = 0;int res = 0;int maxDepth(TreeNode* root) {traverse(root);return res;}// 遍歷二叉樹void traverse(TreeNode* root) {if (root == nullptr) {return;}// 前序遍歷位置depth++;// 遍歷的過程中記錄最大深度res = max(res, depth);traverse(root->left);traverse(root->right);// 后序遍歷位置depth--;}
};

solution 2 分解問題

我們要求一顆二叉樹的最大深度，我們只需要分別知道它的左右子樹的最大深度即可，然后return 1（根節點）+max（leftmax，rightmax）就行了

class Solution2 {// 定義：輸入一個節點，返回以該節點為根的二叉樹的最大深度
public:int maxDepth(TreeNode* root) {if (root == nullptr) {return 0;}int leftMax = maxDepth(root->left);int rightMax = maxDepth(root->right);// 根據左右子樹的最大深度推出原二叉樹的最大深度return 1 + max(leftMax, rightMax);}
};

111.二叉樹的最小深度

算法思路及代碼

solution 1

// 「遍歷」的遞歸思路
class Solution {
private:int minDepthValue = INT_MAX;int currentDepth = 0;void traverse(TreeNode* root) {if (root == nullptr) {return;}// 做選擇：在進入節點時增加當前深度currentDepth++;// 如果當前節點是葉子節點，更新最小深度if (root->left == nullptr && root->right == nullptr) {minDepthValue = std::min(minDepthValue, currentDepth);}traverse(root->left);traverse(root->right);// 撤銷選擇：在離開節點時減少當前深度currentDepth--;}public:int minDepth(TreeNode* root) {if (root == nullptr) {return 0;}traverse(root);return minDepthValue;}
};

solution 2

我覺得有了上一題的鋪墊首先應該是想到這種辦法，思路也非常明確，就是想找到左右子樹各自的最小深度然后再加上根節點 但是力扣給的示例沒有全部通過，它給的示例是一顆斜樹，準確的來說是條五個節點的鏈表，這種就是極端的情況，我們怎么去解決它呢？
根本問題就是要防止當左子樹為空時直接return 0的情況發生（參照下面的預期結果），所以我們就需要在即將離開一個節點之前判斷此時的左右子樹是否為空（也就是leftmin/rightmin為0的情況）
例如 leftmin=0，那么我們就return 1+rightmin（參考根節點的情況）就行了
那為什么在求最大深度的時候不會出現這個問題呢？
給我的感覺： 是因為在求最大深度時，我們的出口是到葉子節點就行（一股腦的往下沖），不會面臨著是否為空的問題，
而我們要求最小深度時其實更像是一個探險的人，需要一步一步地走，需要避開危險

deepseek：
最小深度中，當左子樹為空時(root.left為None)，右子樹的深度決定了當前節點的最小深度。同理處理右子樹為空的情況。只有左右子樹均存在時，才取較小值加1，確保路徑有效。（關鍵）
最大深度直接取左右子樹的最大值加1，無需特殊處理空子樹，因為空子樹的深度0不會影響非空子樹的最大值結果

• 修改之后AC

class Solution {
public:int minDepth(TreeNode* root) {if(root==nullptr){return 0;}int rightmin=minDepth(root->right);int leftmin=minDepth(root->left);if(leftmin==0){return rightmin+1;}if(rightmin==0){return leftmin+1;}return 1+min(leftmin,rightmin);}
};

222.完全二叉樹的結點個數

算法思路和代碼

solution 1

讀完這道題我就有思路了，就是把左右子樹的分別有多少個節點給他算出來，然后相加不就行了嗎 確實能AC，也很簡單
但是這題特意說了是完全二叉樹的節點 意味著我們其實是可以利用完全二叉樹的特性來解決問題的，這才是這題高效率的關鍵，因此就有了solution2

class Solution {
public:int countNodes(TreeNode* root) {if(root==nullptr){return 0;}int left=countNodes(root->left);int right=countNodes(root->right);int result=left+right+1;return result;}
};

solution 2

假如你學習過懶貓老師的課程，你一定知道如果給你一個滿二叉樹的深度k，那么它的節點數就是（2的k次方）-1，而給你一個二叉樹的層數x，那么這一層有2的（X-1）次冪 個節點

#include <cmath>class Solution {
public:int countNodes(TreeNode* root) {TreeNode* l = root;TreeNode* r = root;// 記錄左、右子樹的高度int hl = 0, hr = 0;while (l != nullptr) {l = l->left;hl++;}while (r != nullptr) {r = r->right;hr++;}// 如果左右子樹的高度相同，則是一棵滿二叉樹if (hl == hr) {return (int)pow(2, hl) - 1;}// 如果左右高度不同，則按照普通二叉樹的邏輯計算return 1 + countNodes(root->left) + countNodes(root->right);}
};

110 平衡二叉樹

一棵高度平衡二叉樹定義為：一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過1

算法思路及代碼

solution

對于這道題其實不用想的太復雜，還是一樣，就問你是不是遍歷一遍就可以判斷是否為二叉平衡樹了，怎么判斷呢，是不是把兩個左右子樹高度搞出來，然后比較一下就行了，代碼上就是借助一個外部變量然后一個compare函數就行 需要注意的是定義里提到了絕對值，那么最簡單能準確表達的 就是借助abs絕對值函數，會用就行

• 我們需要知道這個compare函數幫我們做了什么事情，需要明確給出這個函數的定義：返回以該節點為根節點的二叉樹的高度，如果不是平衡二叉樹了則返回-1 不然就很容易被繞進去

• 明確單層遞歸的邏輯
  如何判斷以當前傳入節點為根節點的二叉樹是否是平衡二叉樹呢？當然是其左子樹高度和其右子樹高度的差值。

• 分別求出其左右子樹的高度，然后如果差值小于等于1，則返回當前二叉樹的高度，否則返回-1，表示已經不是二叉平衡樹了。

class Solution {
public:int compare_height(TreeNode* root){if(root==nullptr){return 0;}int left=compare_height(root->left);if(left==-1){return -1;}int right=compare_height(root->right);if(right==-1){return -1;}return abs(left - right) > 1 ? -1 : 1 + max(left, right);}bool isBalanced(TreeNode* root) {int result= compare_height(root);if(result!=-1){return true;}else{return false;}}
};

257 二叉樹的所有路徑

這題其實還是有一些不一樣 回溯的味道非常明顯了 這也是labuladong在它的文章中提到的二叉樹與動態規劃和回溯算法之間的關系

算法思路及代碼

404 左葉子之和

算法思路與代碼

solution

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if(root==nullptr){return 0;}if(root->left==nullptr &&root->right==nullptr)//葉子節點{return 0;}int leftsum=sumOfLeftLeaves(root->left);if(root->left!=nullptr && root->left->left==nullptr && root->left->right==nullptr){leftsum=root->left->val;}int rightsum=sumOfLeftLeaves(root->right);int sum=leftsum+rightsum;return sum;}
};

513 找樹左下角的值

算法思路及代碼

solution1 （遍歷）

對于這題來說 （詳細的過程都在代碼隨想錄）詳細版

• 首先 思路是先用遍歷的方式來解決 一個find函數和一個變量depth就能解決問題
• 其次我們需要確定這個函數的終止條件（遞歸的出口）是不是當遇到葉子節點的時候就需要更新depth了，用一個result記錄此時深度最左邊節點的值
• 再次我們需要給這個find函數一個明確的定義，就是給一個根節點返回，最大深度最左邊孩子的值
• 細節方面 由于求得是最大深度 我們的depth是需要不斷更新的 就是說我們需要一個全局變量保存depth的值 由于我們需要再往下遍歷之前記錄此時的深度 所以還是采用前序遍歷
• 先給MAXdepth先定義成最小的整型，確保MAXdepth能夠正常更新 result同理

class Solution {
public:
int Maxdepth=INT_MIN;
int result;void traverse(TreeNode* root,int depth){if(root->left==nullptr&& root->right==nullptr){//如果找到葉子節點更新最大深度if(depth>Maxdepth){Maxdepth=depth;result=root->val;}return;}if(root->left!=nullptr){depth++;//前序位置traverse(root->left,depth);depth--;//后序位置 回溯（在離開節點時維護depth）}if(root->right!=nullptr){depth++;traverse(root->right,depth);depth--;}return;}int findBottomLeftValue(TreeNode* root) {traverse(root,0);return result;}

solution 2（迭代）

我們只需要在層序遍歷到最后一層時 記錄最后一層的第一個節點即可
利用了C++STL容器和隊列先進先出的特點 定義了一個結點類型的隊列 用于存儲樹的節點 弄個node指向每一層的第一個節點，result記錄每次node指向的值，直到隊空停止循環

class Solution {
public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);int result = 0;while (!que.empty()) {int size = que.size();for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if (i == 0) result = node->val; // 記錄最后一行第一個元素if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return result;}
};

112.路徑總和

算法思路以及代碼

思路概述
我們需要判斷二叉樹中是否存在從根節點到葉子節點的路徑，使得路徑上所有節點值的和等于給定的目標和 targetSum。我們可以通過遞歸的方式實現這一點，具體來說，使用前序遍歷（根-左-右）來遍歷二叉樹。
詳細步驟
定義 findPath 函數：
參數：
cur：當前處理的節點。
sum：當前路徑的累加和。
targetSum：目標和。
返回值：布爾值，表示是否存在從當前節點到葉子節點的路徑，路徑和等于 targetSum。
檢查空節點：
如果當前節點 cur 為空，直接返回 false，因為空節點不可能構成路徑。
累加節點值：
將當前節點的值 cur->val 累加到路徑和 sum 中。
檢查葉子節點：
如果當前節點是葉子節點（即沒有左子節點和右子節點），檢查路徑和 sum 是否等于目標和 targetSum。
如果相等，返回 true，表示找到了滿足條件的路徑。
否則，返回 false。
遞歸檢查左子樹：
遞歸調用 findPath 處理左子樹 cur->left。
如果左子樹中存在滿足條件的路徑，返回 true。
遞歸檢查右子樹：
遞歸調用 findPath 處理右子樹 cur->right。
如果右子樹中存在滿足條件的路徑，返回 true。
返回結果：
如果左右子樹中都沒有找到滿足條件的路徑，返回 false。

solution 1

暴力

一開始我想用一個vector向量來保存每次遞歸到葉子節點sum的值 也就是說需要遍歷出所有路線，然后在主函數中for循環遍歷我們的vector 如果找到了targetsum就return true 找不到就return false

#include <iostream>
#include <vector>using namespace std;// Definition for a binary tree node.
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};class Solution {
public:// 輔助函數，用于遞歸查找路徑和并存儲在 record 向量中void findPath(TreeNode* cur, int sum, int targetSum, vector<int>& record) {// 如果當前節點為空，直接返回if (cur == nullptr) {return;}// 累加當前節點的值到路徑和sum += cur->val;// 檢查當前節點是否是葉子節點（即沒有左子節點和右子節點）if (cur->left == nullptr && cur->right == nullptr) {// 如果是葉子節點，將路徑和添加到 record 向量中record.push_back(sum);return;}// 遞歸檢查左子樹findPath(cur->left, sum, targetSum, record);// 遞歸檢查右子樹findPath(cur->right, sum, targetSum, record);}// 主函數，判斷是否存在路徑和等于目標和bool hasPathSum(TreeNode* root, int targetSum) {vector<int> record; // 用于存儲每條路徑的和findPath(root, 0, targetSum, record); // 調用輔助函數 findPath// 遍歷 record 向量，檢查是否存在等于 targetSum 的路徑和for (int sum : record) {if (sum == targetSum) {return true;}}// 如果沒有找到等于 targetSum 的路徑和，返回 falsereturn false;}
};

但是這個思路確實是太麻煩了是可以去優化的

class Solution {
public:// 輔助函數，用于遞歸查找路徑和bool findPath(TreeNode* cur, int sum, int targetSum) {// 如果當前節點為空，直接返回 falseif (cur == nullptr) {return false;}// 累加當前節點的值到路徑和sum += cur->val;// 檢查當前節點是否是葉子節點（即沒有左子節點和右子節點）if (cur->left == nullptr && cur->right == nullptr) {// 如果路徑和等于目標和，返回 truereturn sum == targetSum;}// 遞歸檢查左子樹，如果左子樹中存在滿足條件的路徑，返回 trueif (findPath(cur->left, sum, targetSum)) {return true;}// 遞歸檢查右子樹，如果右子樹中存在滿足條件的路徑，返回 trueif (findPath(cur->right, sum, targetSum)) {return true;}// 如果左右子樹中都沒有找到滿足條件的路徑，返回 falsereturn false;}// 主函數，判斷是否存在路徑和等于目標和bool hasPathSum(TreeNode* root, int targetSum) {// 調用輔助函數 findPath 從根節點開始查找return findPath(root, 0, targetSum);}
};

solution 2

其實跟方法一在思路上本質上是一樣的

class Solution 2 {
public:// 輔助函數，用于遞歸查找路徑和bool findPath(TreeNode* cur, int sum, int targetSum) {// 如果當前節點為空，直接返回 falseif (cur == nullptr) {return false;}// 累加當前節點的值到路徑和sum += cur->val;// 檢查當前節點是否是葉子節點（即沒有左子節點和右子節點）if (cur->left == nullptr && cur->right == nullptr) {// 如果路徑和等于目標和，返回 truereturn sum == targetSum;}// 遞歸檢查左子樹，如果左子樹中存在滿足條件的路徑，返回 trueif (findPath(cur->left, sum, targetSum)) {return true;}// 遞歸檢查右子樹，如果右子樹中存在滿足條件的路徑，返回 trueif (findPath(cur->right, sum, targetSum)) {return true;}// 如果左右子樹中都沒有找到滿足條件的路徑，返回 falsereturn false;}// 主函數，判斷是否存在路徑和等于目標和bool hasPathSum(TreeNode* root, int targetSum) {// 調用輔助函數 findPath 從根節點開始查找return findPath(root, 0, targetSum);}
};

106 中序與后序遍歷序列構造二叉樹

我覺得一上來就做這題以及后面的同類型題目其實還是比較困難的 因為我們一開始在學習二叉樹的前中后序遍歷時一般都是給我們一顆二叉樹 讓我們給出它的前中后序的遍歷序列 這是一個正向的過程 而本題剛剛好是不是完全相反了啊 所以比較難
希望大家在做這題之前去看一下懶貓老師的視頻 如果不明白C++ STL的map以及它的基本操作 也需要去了解一下
懶貓老師-數據結構-(29)根據二叉樹的遍歷結果確定二叉樹
如果你看完這個視頻 相信你一定對于這題有了最基本的認知，只不過對于代碼實現還是不太清楚
也就是說 你知道給你一個前序和中序/后序遍歷序列，能確定唯一的二叉樹 你在看后面的題目 給你一個前序后序 題目只要你返回任意一顆滿足的二叉樹即可 這就是原因所在
其實我覺得區別這些的關鍵其實就是對于每顆子樹的根節點怎么去找

思路及代碼

主函數是buildTree 輔助函數是build 哈希表inpos的作用就是存儲中序遍歷的值與其位置的映射比如說：后序遍歷的最后一個元素是根節點 我們現在想確定它的左右子樹 那么我們只需要找到這個根節點在中序遍歷上的位置即可 左邊就是左子樹 右邊就是右子樹

solution

il ，ir分別表示前序遍歷序列的左右兩端 pl，pr分別表示后序遍歷的左右兩端（我用AI補全了注釋方便理解）
如果還有不懂的地方直接看視頻就好 我附在這里 真的是講的非常好
106. 從中序與后序遍歷序列構造二叉樹 | 手寫圖解版思路 + 代碼講解

// Solution類用于根據中序和后序遍歷數組構建二叉樹
class Solution {// 使用哈希表存儲中序遍歷中每個值的位置，以便快速查找根節點在中序遍歷中的位置unordered_map<int,int>inpos;
public:/*** 主要的構建函數，接收中序和后序遍歷數組作為輸入* @param inorder 中序遍歷數組* @param postorder 后序遍歷數組* @return 返回構建的二叉樹根節點*/TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int n=inorder.size();// 遍歷中序遍歷數組，記錄每個值的位置for(int i=0;i<n;i++){inpos[inorder[i]]=i;}// 調用build函數開始構建二叉樹return build(inorder,postorder,0,n-1,0,n-1);}/*** 遞歸構建二叉樹的輔助函數* @param inorder 中序遍歷數組* @param postorder 后序遍歷數組* @param il 中序遍歷的左邊界* @param ir 中序遍歷的右邊界* @param pl 后序遍歷的左邊界* @param pr 后序遍歷的右邊界* @return 返回當前遞歸構建的子樹根節點*/TreeNode* build(vector<int>& inorder,vector<int>& postorder,int il,int ir,int pl,int pr){// 如果中序遍歷的左邊界大于右邊界，說明已經沒有節點，返回空指針if(il>ir || pl>pr){return nullptr;}// 計算左子樹的節點個數int k=inpos[postorder[pr]]-il;// 獲取當前子樹的根節點值int rootval=postorder[pr];// 創建根節點TreeNode* root =new TreeNode(rootval);// 遞歸構建左子樹root->left=build(inorder,postorder,il,il+k-1,pl,pl+k-1);// 遞歸構建右子樹root->right=build(inorder,postorder,il+k+1,ir,pl+k,pr-1);// 返回構建的根節點return root;}
};

相關題目

前序中序

TreeNode* constructMaximumBinaryTree([3,2,1,6,0,5]) {// 找到數組中的最大值TreeNode* root = new TreeNode(6);// 遞歸調用構造左右子樹root->left = constructMaximumBinaryTree({3,2,1});root->right = constructMaximumBinaryTree({0,5});return root;
}// 當前 nums 中的最大值就是根節點，然后根據索引遞歸調用左右數組構造左右子樹即可
// 再詳細一點，就是如下偽碼
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {if (nums.empty()) return nullptr;// 找到數組中的最大值int maxVal = INT_MIN;int index = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i] > maxVal) {maxVal = nums[i];index = i;}}TreeNode* root = new TreeNode(maxVal);// 遞歸調用構造左右子樹root->left = constructMaximumBinaryTree(nums[0..index-1]);root->right = constructMaximumBinaryTree(nums[index+1..nums.size()-1]);
}

前序后序（不唯一）

class Solution {// 存儲 postorder 中值到索引的映射unordered_map<int, int> valToIndex;public:TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {for (int i = 0; i < postorder.size(); i++) {valToIndex[postorder[i]] = i;}return build(preorder, 0, preorder.size() - 1,postorder, 0, postorder.size() - 1);}// 定義：根據 preorder[preStart..preEnd] 和 postorder[postStart..postEnd]// 構建二叉樹，并返回根節點。TreeNode* build(vector<int>& preorder, int preStart, int preEnd,vector<int>& postorder, int postStart, int postEnd) {if (preStart > preEnd) {return nullptr;}if (preStart == preEnd) {return new TreeNode(preorder[preStart]);}// root 節點對應的值就是前序遍歷數組的第一個元素int rootVal = preorder[preStart];// root.left 的值是前序遍歷第二個元素// 通過前序和后序遍歷構造二叉樹的關鍵在于通過左子樹的根節點// 確定 preorder 和 postorder 中左右子樹的元素區間int leftRootVal = preorder[preStart + 1];// leftRootVal 在后序遍歷數組中的索引int index = valToIndex[leftRootVal];// 左子樹的元素個數int leftSize = index - postStart + 1;// 先構造出當前根節點TreeNode* root = new TreeNode(rootVal);// 遞歸構造左右子樹// 根據左子樹的根節點索引和元素個數推導左右子樹的索引邊界root->left = build(preorder, preStart + 1, preStart + leftSize,postorder, postStart, index);root->right = build(preorder, preStart + leftSize + 1, preEnd,postorder, index + 1, postEnd - 1);return root;}
};

654 最大二叉樹

思路及代碼

*每個二叉樹節點都可以認為是一棵子樹的根節點，對于根節點，首先要做的當然是把想辦法把自己先構造出來，然后想辦法構造自己的左右子樹。

所以，我們要遍歷數組把找到最大值 maxVal，從而把根節點 root 做出來，然后對 maxVal 左邊的數組和右邊的數組進行遞歸構建，作為 root 的左右子樹。*

solution

class Solution1 {
public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {//遞歸終止條件：只有一個元素的時候if(nums.size()==1)return new TreeNode (nums[0]);//我們需要記錄最大值來輸出 以及索引下標來分隔左子樹 右子樹int maxval=0;int index=0;//遍歷整個數組找到最大值for(int i=0;i<nums.size();i++){if(nums[i]>maxval){maxval=nums[i];index=i;//不斷更新maxval//直到遍歷完整個數組找到最大值}}TreeNode* root=new TreeNode(maxval);//遞歸創建左子樹if(index>0){vector<int>vec(nums.begin(),nums.begin()+index) ;//創建一個數組來存儲左子樹元素范圍root->left=constructMaximumBinaryTree(vec);}//右子樹if(index<nums.size()-1)//說明至少還有一個元素{vector<int>vec2(nums.begin()+index+1,nums.end());root->right=constructMaximumBinaryTree(vec2);}return root;}
};
**************************************
class Solution2 {
public:// 主函數TreeNode* constructMaximumBinaryTree(std::vector<int>& nums) {return build(nums, 0, nums.size() - 1);}// 定義：將 nums[lo..hi] 構造成符合條件的樹，返回根節點TreeNode* build(std::vector<int>& nums, int lo, int hi) {// base caseif (lo > hi) {return nullptr;}// 找到數組中的最大值和對應的索引int index = -1, maxVal = INT_MIN;for (int i = lo; i <= hi; i++) {if (maxVal < nums[i]) {index = i;maxVal = nums[i];}}TreeNode* root = new TreeNode(maxVal);// 遞歸調用構造左右子樹root->left = build(nums, lo, index - 1);root->right = build(nums, index + 1, hi);return root;}
};

二叉搜索樹相關

700.二叉搜索樹中的搜索

算法思路與代碼

就是利用二叉搜索樹左<根<右的特性 使得我們不用去搜索整顆二叉樹去找到target

solution

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(root==nullptr || root->val==val){return root;}       if(root->val>val){return searchBST(root->left,val);}if(root->val<val){return searchBST(root->right,val);}return nullptr;}
};