class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { //递归进行加回溯过程 if(rootq||rootp||rootNULL) return root; TreeNode*leftlowestCommonAncestor(root-left,p,q); TreeNode*rightlowestCommonAncestor(root-right,p,q); if(left!NULLright!NULL) return root;//在左和右返回根 if(leftNULLright!NULL) return right; else if(left!NULLrightNULL) return left; else return NULL; } };普通二叉树需要遍历全部中左右遍历思想1.分别在左和右根为祖先2.p或q为根节点直接返回p或q3.都不在左返回右4.都不在右返回左class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { //比二叉树少了全图遍历//直接找根节点 if(rootNULL) return root; if(root-valp-valroot-valq-val) return lowestCommonAncestor(root-left,p,q); else if(root-valp-valroot-valq-val) return lowestCommonAncestor(root-right,p,q); else return root; } };因为二叉搜索树是有序的所以直接比较大小看在左右1.都在左-》递归进行2.都在右-递归3.分别左右-》返回根class Solution { public: TreeNode* insertIntoBST(TreeNode* root, int val) { //需要保证树的平衡 if(rootnullptr) { TreeNode*nodenew TreeNode(val); return node; } if(root-valval) root-leftinsertIntoBST(root-left,val); if(root-valval) root-rightinsertIntoBST(root-right,val); return root; } };因为不用注意二叉树搜索树的性质直接插入就行比较查找不用遍历全树class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { //1.节点不存在 if(rootnullptr) return nullptr; if(root-valkey) { //2.节点左右为空 if(root-leftnullptrroot-rightnullptr) { delete root; return nullptr; } //3.节点左为空 else if(root-leftnullptr) { //保存右节点返回 TreeNode*noderoot-right; delete root; return node; } //4.右节点为空 else if(root-rightnullptr) { TreeNode*noderoot-left; delete root; return node; } //左右不为空 else { TreeNode*curroot-right; //找右的最左节点 while(cur-left) { curcur-left; } cur-leftroot-left; TreeNode*tmproot; rootroot-right; delete tmp; return root; } } if(root-valkey) root-leftdeleteNode(root-left,key); if(root-valkey) root-rightdeleteNode(root-right,key); return root; } };插入就比较麻烦需要对删除节点进行分析1.不存在返回空2.删除节点左右为空直接删除返回空3.删除节点左节点不存在直接右替代删除节点4.删除节点右节点不存在直接左替代删除节点5.删除节点左右节点都存在将删除节点的左节点放到删除节点的最左节点即可
