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

给定一个二叉搜索树,

递归

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

只要val在p和q之间，那么root就是最近公共祖先

迭代

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.left
            elif root.val < p.val and root.val < q.val:
                root = root.right    
            else:
                return root
        return None

二叉搜索树中的插入操作

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

给定二叉搜索树（BST）的根节点 root 和一个整数值 val ，

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            return TreeNode(val)
        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 or root.val == val:
            return TreeNode(val)
        if val < root.val:
            if not root.left :
                root.left = TreeNode(val)
            else:
                self.insertIntoBST(root.left,val)
        if val > root.val:
            if not root.right:
                root.right = TreeNode(val)
            else:
                self.insertIntoBST(root.right,val)
        return root

删除二叉搜索树中的节点

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

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

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