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;}
};