654.最大二叉樹

分析：相比較遍歷順序構建二叉樹，這個相對簡單。

思路：每次找到數組最大值，然后分割數組

class Solution {
public:TreeNode*judge(vector<int>&nums){if(nums.size()==0) return nullptr;int maxNum=0,index=0;for(int i=0;i<nums.size();i++){//獲取最大值和下標if(nums[i]>maxNum){maxNum=nums[i];index=i;}}TreeNode*root=new TreeNode(maxNum);if(nums.size()==1) return root;//切割左子樹和右子樹vector<int> leftNums(nums.begin(),nums.begin()+index);vector<int> rightNums(nums.begin()+index+1,nums.end());root->left=judge(leftNums);root->right=judge(rightNums);return root;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {//思路：每次找到數組中最大值，然后進行左右切割return judge(nums);}
};

617.合并二叉樹

思路一：創建一個新的二叉樹，每次同時傳入二叉樹的同一位置

class Solution {
public:TreeNode* judge(TreeNode*root1,TreeNode*root2){if(root1==nullptr && root2==nullptr) return nullptr;TreeNode*newNode=new TreeNode();if(root1!=nullptr && root2!=nullptr){newNode->val=root1->val+root2->val;newNode->left=judge(root1->left,root2->left);newNode->right=judge(root1->right,root2->right);} if(root1==nullptr && root2!=nullptr){newNode->val=root2->val;newNode->left=judge(nullptr,root2->left);newNode->right=judge(nullptr,root2->right);} if(root1!=nullptr && root2==nullptr){newNode->val=root1->val;newNode->left=judge(root1->left,nullptr);newNode->right=judge(root1->right,nullptr);} return newNode;}TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {//思路：直接同時遍歷兩個二叉樹，子節點不存在傳入下一個為空指針if(root1==nullptr) return root2;if(root2==nullptr) return root1;if(root1==nullptr && root2==nullptr) return nullptr;return judge(root1,root2);}
};

思路二：以其中一棵二叉樹作為返回值，盡量不創建節點

class Solution {
public:TreeNode* judge(TreeNode*root1,TreeNode*root2){if(root1==nullptr && root2==nullptr) return nullptr;if(root1!=nullptr && root2!=nullptr){root1->val+=root2->val;root1->left=judge(root1->left,root2->left);root1->right=judge(root1->right,root2->right);} else if(root1==nullptr && root2!=nullptr){TreeNode*newNode=new TreeNode();newNode->val=root2->val;newNode->left=judge(nullptr,root2->left);newNode->right=judge(nullptr,root2->right);return newNode;} return root1;}TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {//思路：直接同時遍歷兩個二叉樹，子節點不存在傳入下一個為空指針if(root1==nullptr) return root2;if(root2==nullptr) return root1;if(root1==nullptr && root2==nullptr) return nullptr;root1->val+=root2->val;root1->left=judge(root1->left,root2->left);root1->right=judge(root1->right,root2->right);return root1;}
};

700.二叉搜索樹中的搜索

思路：判斷大小，搜索

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {//思路：找到節點，然后返回//分析：左子節點比父節點小，右子節點比父節點大if(root==nullptr)return root;TreeNode*newNode=root;;if(newNode->val>val)newNode=searchBST(newNode->left,val);else if(newNode->val<val)newNode=searchBST(newNode->right,val);return newNode;}
};

98.驗證二叉搜素樹

思考：從二叉搜索樹的特性入手，二叉搜索樹的中序遍歷必然是遞增序列

分析：細節方面很要注意

class Solution {
public:vector<int>ans;void judge(TreeNode*root){if(root==nullptr) return;judge(root->left);ans.push_back(root->val);judge(root->right);}bool isValidBST(TreeNode* root) {//思路：直接分析//思路二：中序遍歷的數組一定遞增judge(root);if(ans.size()==1) return true;int pre=ans[0];for(int i=1;i<ans.size();i++){if(ans[i]<=pre)return false;pre=ans[i];}return true;}
};

530.二叉搜索樹的最小絕對差

思路：把所有節點加入數組，排序后兩兩計算最小差值

class Solution {
public:vector<int>ans;void judge(TreeNode*root){if(root==nullptr) return;ans.push_back(root->val);judge(root->left);judge(root->right);}int getMinimumDifference(TreeNode* root) {//思路：把父節點的值傳入子節點，然后更新最小差值//問題：題目要求是任意節點，所以考慮先加入數組，排序后兩兩計算judge(root);sort(ans.begin(),ans.end());int minSub=INT_MAX;for(int i=1;i<ans.size();i++){int mid=abs(ans[i-1]-ans[i]);minSub=min(minSub,mid);}return minSub;}
};

501.二叉搜索樹中的眾數

分析：眾數就是出現多次的數
思路：使用哈希表，遞歸遍歷所有節點

class Solution {
public:vector<int>res;unordered_map<int,int>map;void judge(TreeNode*root){if(root==nullptr)return;map[root->val]++;//記錄出現的次數judge(root->left);judge(root->right);}vector<int> findMode(TreeNode* root) {judge(root);int maxNum=0;for(auto it:map){//第一次遍歷獲取出現最大頻率if(it.second>maxNum) maxNum=it.second;}for(auto it:map){//找到眾數if(it.second==maxNum) res.push_back(it.first);}return res;}
};

236.二叉樹的最近公共樹祖先

思路一：通過左0右1獲取兩個節點的遍歷路徑，然后截取兩個節點相同的遍歷路徑，使用相同的遍歷路徑直接獲得最近公共樹祖先

class Solution {
public:string midP="",midQ="";void judge(TreeNode*root,string judgeDist,TreeNode*p,TreeNode*q,string midP1,string midQ1){if(root==nullptr)  return;midP1+=judgeDist;midQ1+=judgeDist;if(root==p) midP=midP1;if(root==q) midQ=midQ1;judge(root->left,"0",p,q,midP1,midQ1);judge(root->right,"1",p,q,midP1,midQ1); }TreeNode*search(TreeNode*root,queue<char> mid,int start){TreeNode*cur;if(mid.size()==0)return root;//分兩種情況if(mid.front()=='1'){mid.pop();cur=search(root->right,mid,start+1);} else{mid.pop();cur=search(root->left,mid,start+1);}  return cur;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//思路：遍歷二叉樹，給左右子節點分別編號，找到兩個節點之后匹配編號的相同位數，//然后用相同位數走到的那個節點就是最近公共祖先int i;queue<char>que;judge(root,"",p,q,"","");//cout<<midP.size()<<midQ.size();for(i=0;i<midP.size();i++){if(midP[i]!=midQ[i]) break;elseque.push(midP[i]);}//cout<<1;if(i==0) return root;string mid=midP.substr(0,i);cout<<mid.size()<<endl;return search(root,que,0);}
};

235.二叉搜索樹的最近公共祖先

思路一：比較出節點值大小，然后從根節點開始判斷兩個節點的位置

class Solution {
public:TreeNode* judge(TreeNode*root,TreeNode*first,TreeNode*second){//祖先節點在當前root上或者兩個節點在當前root的兩邊if((first->val<=root->val && second->val>root->val) || (first->val<root->val && second->val>=root->val)) return root;TreeNode*res;//當前兩個節點在同一邊if(first->val<root->val && second->val<root->val)res=judge(root->left,first,second);else if(first->val>root->val && second->val>root->val)res=judge(root->right,first,second);return res;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//思路：找到一個在兩個節點中間的節點，或者等于較小值//比較出最小值if(p->val>q->val) return judge(root,q,p);return judge(root,p,q);}
};

701.二叉搜索樹的插入操作

思路一：直接遍歷插入

class Solution {
public:void judge(TreeNode*root,int val){if(root->val>val){//需要插入左邊if(root->left) judge(root->left,val);else{TreeNode*newNode=new TreeNode(val);root->left=newNode;}}else{//需要插入右邊if(root->right) judge(root->right,val);else{TreeNode*newNode=new TreeNode(val);root->right=newNode;}}}TreeNode* insertIntoBST(TreeNode* root, int val) {if(root==nullptr){//考慮沒有節點的情況return new TreeNode(val);}judge(root,val);return root;}
};

450.刪除二叉搜索樹的節點

分析：這題做的好復雜，感覺饒了很多彎子，100多行居然還超過了68%哈哈哈哈哈

思路一：

????????????????1.考慮特殊情況，根節點不存在和要刪除根節點。

? ? ? ? ? ? ? ? 2.考慮二叉樹中沒有要刪除的節點。

? ? ? ? ? ? ? ? 3.遞歸遍歷尋找left，或者right是否為要刪除的節點，當找到時，將root和要刪除的子節點傳入res刪除函數，其中變量judgeB判斷是左子節點還是右子節點。

? ? ? ? ? ? ? ? 4.在刪除節點時，需要判斷該節點是否有左右子節點，都有的情況下需要使用add函數，將要刪除的節點的左子節點放到右子節點的下面。使用add遞歸添加

class Solution {
public:bool judgeA=false;void add(TreeNode*root,TreeNode*node){//用于刪除節點時，組合該節點的兩個子節點if(node==nullptr) return;if(root->val>node->val){//插入節點在左邊if(root->left)add(root->left,node);elseroot->left=node;}else{//插入節點在右邊if(root->right)add(root->right,node);elseroot->right=node;}}void res(TreeNode*root,TreeNode*node, bool judgeB){//用于刪除節點if(judgeB)//左子節點{if(node->left==nullptr && node->right==nullptr){//key值節點為葉子節點root->left=nullptr;return;}else if(node->left && node->right){//key值節點有左右節點root->left=node->right;add(node->right,node->left);return;}else if(node->left && !node->right)root->left=node->left;elseroot->left=node->right;}else{if(node->left==nullptr && node->right==nullptr){//key值節點為葉子節點root->right=nullptr;return;}else if(node->left && node->right){//key值節點有左右節點root->right=node->right;add(node->right,node->left);return;}else if(node->left && !node->right)root->right=node->left;elseroot->right=node->right;}}void judge(TreeNode*root,int key){//用于查找刪除節點if(root==nullptr)return;if(root->val>key){//當父節點大于key，說明key在左邊if(root->left->val==key){//當左子節點等于key時res(root,root->left,true);}elsejudge(root->left,key);}else if(root->val<key){if(root->right->val==key){res(root,root->right,false);}elsejudge(root->right,key);}}void judgeMax(TreeNode*root,int key){//用于判斷二叉樹中是否存在目標節點if(root==nullptr) return;if(root->val==key) judgeA=true;if(root->val>key) judgeMax(root->left,key);if(root->val<key) judgeMax(root->right,key);}TreeNode* deleteNode(TreeNode* root, int key) {//思路：遍歷二叉樹，找到節點時，判斷當前節點左右兩邊情況//if(root==nullptr) return root;if(root->val==key){if(root->left && root->right){add(root->right,root->left);return root->right;}else if(root->left) return root->left;else if(root->right) return root->right;elsereturn nullptr;}judgeMax(root,key);if(judgeA==false){cout<<123;return root;} judge(root,key);return root;}
};