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

讲解前：

这道题其实可以用完全一样的code和普通二叉树的公共祖先一样，得到答案，但是那样就完全没有用到BST的特性，我这里的解法其实也不知道是不是用到了BST的特性，我这里觉得既然是二叉搜索树就证明左右子树的整体是比root大或者小的，所以其实在每一个root的时候，如果p和q都同时比root大或者比root小，那么我们就没必要对另外一边的子树进行递归，因为公共祖先肯定不可能在那边，因为那边可能包含p和q的node，所以就只对一边进行递归然后另一边直接设成none

然后呢还有另外一种情况，当我们发现p和q分别一个大于当前root一个小于当前root的时候，我们就可以直接返回root了，因为在二叉搜索树中，这种情况发生的时候，p和q一定分别在我们树的左右两个子树中，意味着他们不可能再有机会有相同的公共祖先了出了当前节点以外

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        
        # base case
        # when we get to the none node or we found either p or q
        if not root:
            return None
        elif root is q or root is p:
            return root
        
        # recursive case
        # since is BST, we can choose whether is need to 
        # traverse 
        # when p an q both exist in the left sub tree
        if p.val < root.val and q.val < root.val:
            left = self.lowestCommonAncestor(root.left, p, q)
            right = None
        elif p.val > root.val and q.val > root.val:
            left = None
            right = self.lowestCommonAncestor(root.right, p, q)
        elif p.val < root.val and q.val > root.val:
            return root
        elif p.val > root.val and q.val < root.val:
            return root

        
        # check what to return
        if left and not right:
            return left
        elif right and not left:
            return right
        else:
            return None

讲解后：

看完了卡哥的解法之后发现卡哥的思路和我是一样的但是代码更加简洁了，因为我们能够直接通过如果pq在树的左右就直接判断是不是最近公共祖先，那就可以直接return root，所以这里其实代码可以简洁很多

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        
        # base case
        # when we get to the none node or we found either p or q
        if not root:
            return None
        
        # recursive case
        # since is BST, we can choose whether is need to 
        # traverse 
        # when p an q both exist in the left sub tree
        if p.val < root.val and q.val < root.val:
            left = self.lowestCommonAncestor(root.left, p, q)
            if left:
                return left
        elif p.val > root.val and q.val > root.val:
            right = self.lowestCommonAncestor(root.right, p, q)
            if right:
                return right
        else:
            return root

也就是说这里我们的base case只需要当遍历到空节点的时候就返回none，然后呢在遍历的时候，需要先确定如果pq在同一边，那么我们就需要进行递归，并且其实如果递归之后发现左边的递归或者右边的递归找到了答案，就直接return 那个答案就行了，如果并不是pq都在同一边，就直接return root就行了

然后呢就是迭代法

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        
        while root:

            if root.val == p.val or root.val == q.val:
                return root
            elif (p.val < root.val and q.val > root.val) or (q.val < root.val and p.val > root.val):
                return root

            elif p.val < root.val and q.val < root.val:
                root = root.left
            else:
                root = root.right

其实就是当root不为空的时候，我们就在while循环中遍历，然后呢当我们发现root已经变成了p或者q的其中一个的时候，就可以直接return root了，然后呢如果p和q分别在左右子树之中，就直接return当前的根节点，不是这种情况的话，就根据pq都大或者都小来左右遍历

---

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

讲解前：

我的这个解法其实有一点点不完美，edge case还需要在最后处理，总体思想其实也很简单，我们其实就是通过递归然后直到我们为val找到了一个位置，然后就把val加入到那个root相应的左右节点，这就是base case，然后呢左右递归的时候，只需要注意要遵循二叉搜索树的条件就可以了，就是val如果比root小就往左遍历，大就往右遍历

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:

        def dfs(root, val):
            # base case is when we found a empty spot
            if not root.left and val < root.val:
                root.left = TreeNode(val)
                return 
            elif not root.right and val > root.val:
                root.right = TreeNode(val)
                return
            
            # recursive case to keep going 
            if root.left and val < root.val:
                dfs(root.left, val)
            elif root.right and val > root.val:
                dfs(root.right, val)
        
        if not root:
            return TreeNode(val)
        else:
            dfs(root, val) 
            return root

讲解后：

卡哥对于这道题的解法是通过在base case那里遍历到空节点之后呢，创建一个val 的节点然后呢返回，所以当我们在递归的时候对每一个节点就直接让他的left或者right指向递归的函数，但是我觉得这种方法还是有一点点不好理解对于其他root是怎么一层一层返回上去的，我的解法属于直接赋值然后return结束递归的方法

Leetcode 450. 删除二叉树

讲解前:

这道题还是很有难度的，有非常多的细节需要考虑，我觉得如果直接自己尝试去做的话可能会花费很多的时间debug所以我打算直接看视频来做

讲解后：

看完了卡哥的讲解之后思路就变得非常清晰了，这道题其实就是一开始的思路就要搞对，也就是我们总体的思路是在base case的时候就对节点进行删除，所以我们base case进去之前要比较root.val == key，其次删除的方法是利用返回节点的方式，设想成就像链表一样，我们删除的时候是用被删除的节点的父节点然后指向删除节点的子节点，把删除的节点跳过的操作，所以在base case的处理中我们用的是return root.left 或者 return root.right的操作，然后呢在递归的时候就如果需要向左遍历，就root.left = deleteNode(root.left) 

唯一比较难的就是第五种可能，就是要删除的节点左右都有节点的情况，就如我下图中画的一样

这里我们要把14删除，意味着比14小的10为根的子树需要找一个新的父节点，那么应该找什么呢，其实就是出了14以外当时再大一点的节点，就可以当父节点了，那么就是16，因为16在14的右子树中，代表他比他大，16同时又是14右子树中最左边的节点，意味着他是14右子树中最小的那一个，所以我们就让16的左节点指向10（这里箭头朝向我画错了），然后呢再让3的右节点直接指向20就可以了

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:

        # base case when we found the node 
        # case 1: we couldn't find the node
        if not root:
            return None
        
        if root.val == key:
        # case 2: the node is a leaf node
        # delete the node by return None to its parent
            if not root.left and not root.right:
                return None
        
        # case 3: the node only has left child 
            elif root.left and not root.right:
                return root.left
        
        # case 4: the node only has right child
            elif not root.left and root.right:
                return root.right
            
        # case 5: it has both child
            else:
                cur = root.right
                while cur.left:
                    cur = cur.left
                
                cur.left = root.left
                return root.right
        
        if key < root.val: root.left = self.deleteNode(root.left, key)
        if key > root.val: root.right = self.deleteNode(root.right, key)
        
        return root