算法day18|235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点

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

1.一般性解法

class Solution {
public:TreeNode* traversal(TreeNode* root, TreeNode* p, TreeNode* q){if(root==NULL)return root;if(root==p||root==q)return root;TreeNode* left=traversal(root->left,p,q);TreeNode* right=traversal(root->right,p,q);if(left!=NULL&&right!=NULL)return root;else if(left==NULL&&right!=NULL)return right;else if(left!=NULL&&right==NULL)return left;elsereturn NULL;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {return traversal(root,p,q);}
};

注意

else if(left!=NULL&&right==NULL)return left;

这里返回的是left，而不是root->left。我们需要返回的是从左孩子传上来的值，而不是左孩子结点。

2.递归法

class Solution {
public:TreeNode* traversal(TreeNode* root, TreeNode* p, TreeNode* q){if(root==NULL)return NULL;if(root->val>p->val&&root->val>q->val){TreeNode*left=traversal(root->left,p,q);if(left!=NULL)return left;}else if(root->val<p->val&&root->val<q->val){TreeNode*right=traversal(root->right,p,q);if(right!=NULL)return right;}return root;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {return traversal(root,p,q);}
};

二叉搜索树的另一个利用思路：除了利用二叉树搜索树的中序遍历之外，我们也可以直接利用二叉搜索树在树上的性质：左<中<右。由于没有用到中序遍历的递增序列，所以在递归的时候可以不使用中序遍历，直接用它的性质来接就行了。

核心思路：如果结点值 > p和q的值，那么说明p和q在该节点左边，所以需要向左递归；如果结点值 < p和q的值，那么说明p和q在该节点右边，所以需要向右递归；如果节点值在p和q之间，那么这个结点就是最近的公共祖先。

代码细节：如果函数有返回值，那么在if和else之外一定还需要有一个return，所以这样是错的：

else if(root->val<p->val&&root->val<q->val){TreeNode*right=traversal(root->right,p,q);if(right!=NULL)return right;}
elsereturn root;}

但是改成这样就对了，在 if 和 else 之外再加一个return：

else if(root->val<p->val&&root->val<q->val){TreeNode*right=traversal(root->right,p,q);if(right!=NULL)return right;}
else
{return root;
}     return NULL;}

3.迭代法

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {while(root!=NULL){if(root->val>p->val&&root->val>q->val){root=root->left;}else if(root->val<p->val&&root->val<q->val){root=root->right;}elsereturn root;}return NULL;}
};

701.二叉搜索树中的插入操作

1.递归法

比较简单，代码如下：

class Solution {
public:void traversal(TreeNode* &root, int val){if(root==nullptr){root=new TreeNode(val);return;}if(root->val<val){if(root->right)traversal(root->right,val);else{TreeNode*node=new TreeNode(val);root->right=node;}}if(root->val>val){if(root->left)traversal(root->left,val);else{TreeNode*node=new TreeNode(val);root->left=node;}}return;}TreeNode* insertIntoBST(TreeNode* root, int val) {traversal(root,val);return root;}
};

**核心思路：**当结点值 > root，且右孩子不为空，则向右递归。若右孩子为空，则直接插入，作为该节点的右孩子；当节点值 < root时同理。

易错：

void traversal(TreeNode* &root, int val)

这里需要“带回去”，所以要加上&。

2.迭代法

class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if(root==nullptr){root=new TreeNode(val);return root;}TreeNode*cur=root;TreeNode*parent=cur;while (cur != NULL) {parent = cur;if (cur->val > val) cur = cur->left;else cur = cur->right;}TreeNode*node=new TreeNode(val);if(parent->val<val)parent->right=node;elseparent->left=node;return root;}
};

思路与递归法一致。

450.删除二叉搜索树中的节点

这题难度不小，第一遍尽量理解：

class Solution {
public:TreeNode* traversal(TreeNode* root, int key){if(root==nullptr)return nullptr;if(root->val==key){if(root->left==nullptr&&root->right==nullptr){delete root;return nullptr;}else if(root->left!=nullptr&&root->right==nullptr){TreeNode*temp=root->left;delete root;return temp;}else if(root->left==nullptr&&root->right!=nullptr){TreeNode*temp=root->right;delete root;return temp;}else if(root->left!=nullptr&&root->right!=nullptr){TreeNode*cur=root->right;TreeNode*temp=root->right;while(cur->left)cur=cur->left;cur->left=root->left;delete root;return temp;}}if(root->val>key)root->left=traversal(root->left,key);if(root->val<key)root->right=traversal(root->right,key);return root;}TreeNode* deleteNode(TreeNode* root, int key) {return traversal(root,key);}
};

总体思路：

• 参数和返回值正常

• 终止条件：

  这题的终止条件是重中之重，因为核心条件的判断也纳入了终止条件，即只要符合某种条件就终止。这个条件就是节点值等于key，因为只要节点值等于key就不用再继续递归了。所以真正删除的核心操作就在终止条件里，一共有4种情况：

  • 左右孩子都空，即为叶节点

  • 左孩子空，右孩子不空

  • 左孩子不空，右孩子空

  • 左右孩子都不空（注意这里可以有两种处理逻辑，只要能满足二叉搜索树的定义即可

• 单层递归逻辑：不用对当前结点做处理，只有满足一定条件时才会有处理（即终止条件）