代碼隨想錄算法訓練營第60期第十七天打卡

? ? ? ?今天我們繼續進入二叉樹的下一個章節，今天的內容我在寫今天的博客前大致看了一下部分題目難度不算大，那我們就進入今天的題目。

第一題對應力扣編號為654的題目最大二叉樹

? ? ? ?這道題目的坑相當多，我第一次題目沒有看明白就是我不知道到底是如何構造出這棵二叉樹的，我就直接看了視頻講解，現在我們先來看一下題目：

? ? ? ? 我們先看一下示例是什么意思，注意力扣上是這樣解釋的：

? ? ? ? 首先找出最大值，然后分割數組找到左邊部分與右邊部分然后遞歸構造出根節點的左子樹與右子樹就可以了，這樣我才明白這道題目究竟是什么意思，既然要構造二叉樹大家記住，我們大概率會選用前序遍歷，為什么呢？因為我們構造二叉樹一定是先要從根節點出發才能逐步構建起它的左子樹與右子樹進而遞歸構造出整棵二叉樹，這個是大家一定要去了解的，后來看完講解我發現這道題與我們昨天的最后一道題有異曲同工之妙，其實都還是遞歸構建，當然我們這里是需要先找出最大的元素作為根節點，隨后我們就可以找到左子樹與右子樹，遞歸構建就可以了，我要說明一下注意我們后來的數組是左閉右開的，一定注意，我們傳入數組遞歸構建就可以，我將代碼放到下面大家可以自行參考：

class Solution {
public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {TreeNode* node = new TreeNode(0);//特殊情況要考慮上不要忘記if (nums.size() == 1) return new TreeNode(nums[0]);//那為什么沒有考慮數組為空的情況呢？因為題目說了數組的大小是大于等于1的int maxValue = 0;//定義最大值int index = 0;//定義最大值的下標for (int i = 0; i < nums.size(); ++i){if (nums[i] > maxValue){maxValue = nums[i];index = i;}}node -> val = maxValue;//構造左子樹if (index > 0){vector<int> newVec(nums.begin(), nums.begin() + index);node->left = constructMaximumBinaryTree(newVec);}//構造右子樹if (index < (nums.size() - 1)){vector<int> newVec(nums.begin() + index + 1, nums.end());node -> right = constructMaximumBinaryTree(newVec);}return node;}
};

? ? ? ?那其實這道題目還有優化版本的代碼大家可以發現我需要構造新的數組來存儲左右子數，這樣其實又耗時又耗空間，這里我再給出優化版的代碼：

class Solution {
private:// 在左閉右開區間[left, right)，構造二叉樹TreeNode* traversal(vector<int>& nums, int left, int right) {if (left >= right) return nullptr;// 分割點下標：maxValueIndexint maxValueIndex = left;for (int i = left + 1; i < right; ++i) {if (nums[i] > nums[maxValueIndex]) maxValueIndex = i;}TreeNode* root = new TreeNode(nums[maxValueIndex]);// 左閉右開：[left, maxValueIndex)root->left = traversal(nums, left, maxValueIndex);// 左閉右開：[maxValueIndex + 1, right)root->right = traversal(nums, maxValueIndex + 1, right);return root;}
public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {return traversal(nums, 0, nums.size());}
};

? ? ? ? 這樣就可以避免申請新的空間來重新建立數組，我們直接使用下標操作，不過建議大家先把最基礎的版本搞明白其實就可以了。這道題目我就先分享到這里，接下來我們看下一道題目。

第二題對應力扣編號為617的題目合并二叉樹

? ? ? ? 那這道題是什么意思呢？其實是將兩棵樹相對應位置的節點的數值相加最后可以得到一棵新的二叉樹，我們來看一下具體的題目：

? ? ? ??我們應該如何考慮這道題目呢？其實這道題目難點就在于它是同時操作兩棵二叉樹，而我們平時刷的題都是操作一棵二叉樹，但是我希望這道題過后大家可以掌握應該如何同時操作兩棵二叉樹，首先大家要知道一點就是如果我在合并的過程中我如果其中一棵二叉樹的當前的節點是空，其實我的新合并出來的二叉樹就應該是另一棵二叉樹的所對應節點的值，如果兩棵二叉樹都為空，那其實新二叉樹的對應節點也為空，隨后我們遞歸構建左子樹與右子樹就可以，最后返回根節點，當然我下面提供的代碼是我在tree1的基礎上更新，其實大家也可以開一棵新的二叉樹，在這里我就提供一下更新版本的代碼，如果開新的二叉樹版本大家感興趣的話可以去代碼隨想錄網站去看：

class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if (root1 == NULL) return root2;if (root2 == NULL) return root1;//if (root1 == NULL && root2 == NULL) return NULL;//其實兩棵樹的對應節點都為空的情況已經包含了(上面這一句可以不寫)root1 -> val += root2 -> val;root1 -> left = mergeTrees(root1 -> left, root2 -> left);root1 -> right = mergeTrees(root1 -> right, root2 -> right);return root1;}
};

第三題對應力扣編號為700的二叉搜索樹中的搜索

? ? ? ? ?在這里我們就引入了二叉搜索樹了，我們先復習一下什么樣的樹叫做二叉搜索樹，其實是左子樹的所有數值小于根節點，右子樹的所有數值大于根節點就是二叉搜索樹，我們了解了定義以后我們一起來看一下題目：

? ? ? ?我看到示例就大致明白了題目的具體要求了，其實題目給我們的是一個層序遍歷和一個節點的值，要求我們返回以該節點為根的子樹，那我們如何解決這道題目呢？其實這道題目的遞歸法與迭代法都不難理解，我兩種思路都給大家展示一下，首先題目就很好利用了二叉搜索樹的性質，其實我們是可以利用二叉搜索樹的性質來判斷我們當前搜索的是在左子樹還是右子樹，就是與根節點的值進行比較，如果小就說明我們目前在左子樹，如果大說明我們目前在右子樹，那這樣我們可以寫出如下的遞歸代碼：

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if (root == NULL || root -> val == val) return root;TreeNode* result = NULL;//這時候在左子樹if (root -> val > val){//注意我們使用一個臨時變量來存儲我們找到的值result = searchBST(root -> left, val);}//這時候在右子樹 else if (root -> val < val){result = searchBST(root -> right, val);}return result;}
};

? ? ? ? ? 接下來我們來看一下迭代法如何寫，其實我們原來是不是寫過迭代法，我們一些用到迭代法都是會用棧或者隊列去模擬深度遍歷和廣度遍歷，但這里我們考慮到二叉搜索樹的特殊性，其實我們不需要這么麻煩了，它的節點是有序的我們就不需要四處搜索了，我們看一下代碼是如何寫的：

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

第四題驗證二叉搜索樹對應力扣編號98

? ? ? ? 我們上一道題已經刷到過關于二叉搜索樹的題目，這一道題是讓我們驗證二叉搜索樹，我們看一下題目到底是怎么說的：

? ? ? ? 其實題目要求很簡單了，那么我們應該如何解決呢？其實這道題目有點那種數學題的感覺叫做“會者不難，難者不會”，我為啥這樣說呢？因為如果大家知道一個二叉搜索樹的性質其實就很簡單了，我直接告訴大家，大家以后記住就可以了“中序遍歷下，輸出的二叉搜索樹節點的數值是有序序列”，只要大家知道這個性質其實代碼就很好寫了，我們使用我們之前的迭代寫法將這棵樹的中序遍歷的結果存儲到一個數組里，然后判斷這個數組是否有序就可以了，我可以直接給出代碼：

class Solution {
private:vector<int> vec;void traversal(TreeNode *root){if (root == NULL) return;//左根右的中序遍歷if (root -> left) traversal(root -> left);vec.push_back(root -> val);if (root -> right) traversal(root -> right);}
public:bool isValidBST(TreeNode* root) {vec.clear();//先清空traversal(root);//這樣其實就將數組再次填滿了for (int i = 1; i < vec.size(); ++i){if (vec[i] <= vec[i - 1]) return false;}return true;}
};

? ? ? 這是一種最為直觀的做法，大家務必要將這個技巧牢記于心，那其實還有其他方法，我們還是要注意我們二叉搜索樹是左子樹所有的節點都是小于根節點的，右子樹所有的節點都是大于根節點的，千萬不要不判斷根節點與它的左右孩子的關系，這樣是無法判斷是不是二叉搜索樹的，因為不符合我們二叉搜索樹的定義，那我們應該如何判斷呢？其實我們還是可以使用遞歸的，我們其實可以一直中序遍歷，只要發現沒有順序的就可以直接return false，那我們的代碼可以這樣寫：

class Solution {
public:long long maxVal = LONG_MIN; // 因為后臺測試數據中有int最小值bool isValidBST(TreeNode* root) {if (root == NULL) return true;bool left = isValidBST(root->left);// 中序遍歷，驗證遍歷的元素是不是從小到大if (maxVal < root->val) maxVal = root->val;else return false;bool right = isValidBST(root->right);return left && right;}
};

? ? ? ?就是說我們一直更新maxVal如果左子樹的節點小于根節點的值那我就一直賦值如果發現有大于的這在左子樹這邊就說明不是二叉搜索樹了，我們來看一下代碼：

class Solution {
public:long long maxVal = LONG_MIN;bool isValidBST(TreeNode* root) {if (root == NULL) return true;bool left = isValidBST(root -> left);if (maxVal < root -> val) maxVal = root -> val;else return false;bool right = isValidBST(root -> right);return left && right;}
};

? ? ? ? 這個其實還是中序遍歷，左根右的順序，我們先看左子樹，只要當前節點不為空就一直遞歸，先左再右，最后發現到了葉子節點，最后將根節點賦值給maxVal，接著去判斷右邊，如果最后左右都為true就是二叉搜索樹了，這個遞歸還有點難度，就是我們是如何遞歸的，先左一直到葉子節點會返回true,隨后我們賦值，再去判斷右子樹，當右子樹也到了葉子節點的時候也會返回 true,根節點的右子樹是一個意思，最后我們判斷是否是true，我還是建議大家用上面的第一種方法理解，這個遞歸作為選學，上面的那一種方法必須會。