106. 从中序与后序遍历序列构造二叉树106. 从中序与后序遍历序列构造二叉树
class Solution { public: TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { if(inorder.empty()||postorder.empty())return NULL; TreeNode*root=new TreeNode(postorder.back()); auto it=find(inorder.begin(),inorder.end(),root->val); int index=it-inorder.begin(); vector<int>leftin(inorder.begin(),inorder.begin()+index); vector<int>rightin(inorder.begin()+index+1,inorder.end()); vector<int>leftpost(postorder.begin(),postorder.begin()+index); vector<int>rightpost(postorder.begin()+index,postorder.end()-1); TreeNode*left=buildTree(leftin,leftpost); TreeNode*right=buildTree(rightin,rightpost); root->left=left; root->right=right; return root; } }; 98. 验证二叉搜索树（遍历+中序 二叉搜索树具有中序性质）
class Solution { public: long long pre=LLONG_MIN; bool isValidBST(TreeNode* root) { if(root==NULL)return true; if(!isValidBST(root->left))return false; if(pre>=root->val){ return false; } else pre=root->val; return isValidBST(root->right); } };530. 二叉搜索树的最小绝对差
class Solution { public: int result=INT_MAX; TreeNode*pre=NULL; void tra(TreeNode*root){ if(root==NULL)return; tra(root->left); if(pre!=NULL){ int min=root->val-pre->val; if(result>min)result=min; } pre=root; tra(root->right); return; } int getMinimumDifference(TreeNode* root) { tra(root); return result; } };501. 二叉搜索树中的众数
class Solution { public: int index=0; TreeNode*pre=NULL; int now=1; vector<int>result; void tra(TreeNode* root){ if (root==NULL)return ; tra(root->left); if (pre == NULL || pre->val != root->val) { now = 1; } else { now++; } if(now==index){ result.push_back(root->val); } if(now>index){ result.clear(); result.push_back(root->val); index=now; } pre=root; tra(root->right); } vector<int> findMode(TreeNode* root) { tra(root); return result; } };236. 二叉树的最近公共祖先
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root==NULL)return NULL; if(root==p||root==q)return root; TreeNode*left=lowestCommonAncestor(root->left,p,q); TreeNode*right=lowestCommonAncestor(root->right,p,q); if(left!=NULL&&right!=NULL)return root; else if(left!=NULL)return left; return right; } };450.删除二叉搜索树中的节点
class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { if(root==NULL)return nullptr; if(root->val>key) root->left=deleteNode(root->left,key); else if(root->val<key)root->right=deleteNode(root->right,key); else{ TreeNode*tmp=root->right; if(tmp!=NULL){ while(tmp->left!=nullptr){ tmp=tmp->left; } tmp->left=root->left; root=root->right;} else root=root->left; } return root; } };108. 将有序数组转换为二叉搜索树
class Solution { public: TreeNode* sortedArrayToBST(vector<int>& nums) { if(nums.empty())return NULL; int min=nums.size()/2; TreeNode*root=new TreeNode(nums[min]); vector<int>left1(nums.begin(),nums.begin()+min); vector<int>right1(nums.begin()+min+1,nums.end()); TreeNode*left=sortedArrayToBST(left1); TreeNode*right=sortedArrayToBST(right1); root->left=left; root->right=right; return root; } };
