106. 从中序与后序遍历序列构造二叉树106. 从中序与后序遍历序列构造二叉树​ ​ class Solution { public: TreeNode* buildTree(vectorint inorder, vectorint postorder) { if(inorder.empty()||postorder.empty())return NULL; TreeNode*rootnew TreeNode(postorder.back()); auto itfind(inorder.begin(),inorder.end(),root-val); int indexit-inorder.begin(); vectorintleftin(inorder.begin(),inorder.begin()index); vectorintrightin(inorder.begin()index1,inorder.end()); vectorintleftpost(postorder.begin(),postorder.begin()index); vectorintrightpost(postorder.begin()index,postorder.end()-1); TreeNode*leftbuildTree(leftin,leftpost); TreeNode*rightbuildTree(rightin,rightpost); root-leftleft; root-rightright; return root; } }; ​ ​98. 验证二叉搜索树遍历中序 二叉搜索树具有中序性质class Solution { public: long long preLLONG_MIN; bool isValidBST(TreeNode* root) { if(rootNULL)return true; if(!isValidBST(root-left))return false; if(preroot-val){ return false; } else preroot-val; return isValidBST(root-right); } };530. 二叉搜索树的最小绝对差class Solution { public: int resultINT_MAX; TreeNode*preNULL; void tra(TreeNode*root){ if(rootNULL)return; tra(root-left); if(pre!NULL){ int minroot-val-pre-val; if(resultmin)resultmin; } preroot; tra(root-right); return; } int getMinimumDifference(TreeNode* root) { tra(root); return result; } };501. 二叉搜索树中的众数class Solution { public: int index0; TreeNode*preNULL; int now1; vectorintresult; void tra(TreeNode* root){ if (rootNULL)return ; tra(root-left); if (pre NULL || pre-val ! root-val) { now 1; } else { now; } if(nowindex){ result.push_back(root-val); } if(nowindex){ result.clear(); result.push_back(root-val); indexnow; } preroot; tra(root-right); } vectorint findMode(TreeNode* root) { tra(root); return result; } };236. 二叉树的最近公共祖先class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(rootNULL)return NULL; if(rootp||rootq)return root; TreeNode*leftlowestCommonAncestor(root-left,p,q); TreeNode*rightlowestCommonAncestor(root-right,p,q); if(left!NULLright!NULL)return root; else if(left!NULL)return left; return right; } };450.删除二叉搜索树中的节点class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { if(rootNULL)return nullptr; if(root-valkey) root-leftdeleteNode(root-left,key); else if(root-valkey)root-rightdeleteNode(root-right,key); else{ TreeNode*tmproot-right; if(tmp!NULL){ while(tmp-left!nullptr){ tmptmp-left; } tmp-leftroot-left; rootroot-right;} else rootroot-left; } return root; } };108. 将有序数组转换为二叉搜索树class Solution { public: TreeNode* sortedArrayToBST(vectorint nums) { if(nums.empty())return NULL; int minnums.size()/2; TreeNode*rootnew TreeNode(nums[min]); vectorintleft1(nums.begin(),nums.begin()min); vectorintright1(nums.begin()min1,nums.end()); TreeNode*leftsortedArrayToBST(left1); TreeNode*rightsortedArrayToBST(right1); root-leftleft; root-rightright; return root; } };