代码随想录算法训练营第22天 |二叉树part07：235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点

235.二叉搜索树的最近公共祖先
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/
代码随想录：
https://programmercarl.com/0235.二叉搜索树的最近公共祖先.html
701.二叉搜索树中的插入操作
https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/
代码随想录：
https://programmercarl.com/0701.二叉搜索树中的插入操作.html
701.二叉搜索树中的插入操作
https://leetcode.cn/problems/delete-node-in-a-bst/description/
450.删除二叉搜索树中的节点
https://programmercarl.com/0450.删除二叉搜索树中的节点.html#算法公开课

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

题解思路

• 递归法 利用二叉搜索树的特性 将root.val和p.val和q.val对比 如果属于一边 就搜索该边 否则 就是返回该node
• 迭代:满足条件就顺边找，不满足条件就直接跳出；

题解代码

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return None
        if root.val>q.val and root.val>p.val:
            return self.lowestCommonAncestor(root.left,p,q)
        elif root.val<p.val and root.val <q.val:
            return self.lowestCommonAncestor(root.right,p,q)
        else:
            return root

```python
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while root:
            if root.val <p.val and root.val<q.val:
                root = root.right
            elif root.val>q.val and root.val>p.val:
                root = root.left
            else:
                return root
        return None

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

题解思路

• 递归法：如果小于val，插入左边；如果大于val，插入右边；
• 迭代法：找到需要插入的根节点，直接在根节点插入；

题解代码

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            node = TreeNode(val)
            return node
        if root.val>val:
            root.left = self.insertIntoBST(root.left,val)
        else:
            root.right = self.insertIntoBST(root.right,val)
        return root

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            node = TreeNode(val)
            return node
        curr = root
        pre = None
        while curr:
            pre = curr
            if curr.val > val:
                curr = curr.left
            else:
                curr = curr.right
        node = TreeNode(val)
        if val<pre.val:
            pre.left = node
        else:
            pre.right = node
        return root

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

题解思路：

• 根据二叉搜索树的性质；判断哪个子树需要删除；
• 遇到需要删除的节点：
  • 无左子树；
  • 无右子树；
  • 左右子树都有；

题解代码：

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return root
        if root.val==key:
            if not root.right:
                return root.left
            elif not root.left:
                return root.right
            else:
                curr = root.right
                while curr.left:
                    curr = curr.left
                curr.left = root.left
                return root.right
        elif root.val>key:
            root.left = self.deleteNode(root.left,key)
        else:
            root.right = self.deleteNode(root.right,key)
        return root