654.最大二叉樹

又是構造二叉樹，昨天大家剛剛做完 中序后序確定二叉樹，今天做這個 應該會容易一些， 先看視頻，好好體會一下 為什么構造二叉樹都是 前序遍歷

題目鏈接/文章講解：代碼隨想錄

視頻講解：又是構造二叉樹，又有很多坑！| LeetCode：654.最大二叉樹_嗶哩嗶哩_bilibili

/*** 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:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {TreeNode* node=new TreeNode(0);if (nums.size()==1){node->val=nums[0];return node;}int maxvalue=0;int maxvalueindex=0;if (nums.size()==1)return node;for (int i=0;i<nums.size();i++){if (maxvalue<nums[i]){maxvalue=nums[i];maxvalueindex=i;}}node->val=maxvalue;if (maxvalueindex>0){vector<int> leftnums{nums.begin(),nums.begin()+maxvalueindex};node->left=constructMaximumBinaryTree(leftnums);}if (maxvalueindex<nums.size()-1){vector<int>rightnums{nums.begin()+maxvalueindex+1,nums.end()};node->right=constructMaximumBinaryTree(rightnums);}return node;}
};

617.合并二叉樹

這次是一起操作兩個二叉樹了， 估計大家也沒一起操作過兩個二叉樹，也不知道該如何一起操作，可以看視頻先理解一下。 優先掌握遞歸。

題目鏈接/文章講解：代碼隨想錄

視頻講解：一起操作兩個二叉樹？有點懵！| LeetCode：617.合并二叉樹_嗶哩嗶哩_bilibili

/*** 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:void traversal(TreeNode* node1,TreeNode* node2){if (node1 && node2)node1->val+=node2->val;if (node1->left && node2->left)traversal(node1->left, node2->left);if (node1->right && node2->right)traversal(node1->right,node2->right);if (!node1->left)node1->left=node2->left;if (!node1->right)node1->right=node2->right;}TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if ((!root1 && !root2) || (root1 && !root2))return root1;if (!root1 && root2)return root2;traversal(root1,root2);return root1;}
};

總結

這里有對當前節點的判斷，還有對下面左右節點的判斷。

700.二叉搜索樹中的搜索

遞歸和迭代 都可以掌握以下，因為本題比較簡單， 了解一下 二叉搜索樹的特性

題目鏈接/文章講解: 代碼隨想錄

視頻講解：不愧是搜索樹，這次搜索有方向了！| LeetCode：700.二叉搜索樹中的搜索_嗶哩嗶哩_bilibili

/*** 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:TreeNode* traversal(TreeNode* node,TreeNode*res,int val){if (!node || res)return res;if (node->val==val)res=node;if (node->val>val)res=traversal(node->left, res,val);if (node->val<val)res=traversal(node->right,res,val);return res;}TreeNode* searchBST(TreeNode* root, int val) {TreeNode* res=NULL;return traversal(root,res,val);}};

98.驗證二叉搜索樹

遇到 搜索樹，一定想著中序遍歷，這樣才能利用上特性。

但本題是有陷阱的，可以自己先做一做，然后在看題解，看看自己是不是掉陷阱里了。這樣理解的更深刻。

題目鏈接/文章講解：代碼隨想錄

視頻講解：你對二叉搜索樹了解的還不夠！ | LeetCode：98.驗證二叉搜索樹_嗶哩嗶哩_bilibili

/*** 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:void traversal(TreeNode* node,vector<int>&res){if (!node)return;traversal(node->left,res);res.push_back(node->val);traversal(node->right,res);}bool isValidBST(TreeNode* root) {if (!root)return true;vector<int>res;traversal(root,res);for (int i=1;i<res.size();i++)if (res[i]<=res[i-1])return false;return true;}
};

總結

虧我用回溯解了半天。