算法day22|235，701，450

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        #左右中，使用后序遍历
        #终止条件
        if root is None:
            return root
        #如果根节点的值为q或者p，那么返回节点
        if root == q or root == p:
            return root
        #单层逻辑
        #左右中
        #需要有返回值，因为需要传递节点
        left = self.lowestCommonAncestor(root.left,p,q)
        right = self.lowestCommonAncestor(root.right,p,q)
        if left is None and right is None:  
            return None
        if left is None and right is not None:
            return right
        elif left is not None and right is None:
            return left
        else:
            return root 

三天后写出来了，说明ac了呜呜呜

相对于 二叉树的最近公共祖先 本题就简单一些了，因为 可以利用二叉搜索树的特性。

使用二叉树的特性，不需要全部都遍历，根节点的数值永远都比左子树的大，永远都比右子树的小

迭代法：

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 

递归法：

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def traversal(root,p,q):
            #递归法
            #终止条件
            if root is None:
                return root
            #单层逻辑
            #左边
            if root.val > p.val and root.val >q.val:
                left = traversal(root.left,p,q)
                if left is not None:
                    return left  
            #右边
            if root.val < p.val and root.val 
                right = traversal(root.right,p,q)
                if right is not None:
                    return right
            return root
        return traversal(root,p,q)

二刷：

（未ac） 哭了，没有真正掌握

var lowestCommonAncestor = function(root, p, q) {
    const find = function(root,p,q){
        // 终止条件
        if(root === null){
            return null
        }
        // 往左递归
        if(root.val > q.val && root.val > p.val){
            let left = find(root.left,p,q)
            if(left != null){
                return left
            }
        }
        // 往右递归
        else if(root.val < q.val && root.val < p.val){
            let right = find(root.right,p,q)
            if(right != null){
                return right;
            }
        }else{
        // 如果在中间，根节点就是它的结果
        return root;
        }
    }
    return find(root,p,q)
    
};

迭代法

var lowestCommonAncestor = function(root, p, q) {
    // 迭代法
    while(root){
        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
        }else{
            return root
        }
    }
    return null
};

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

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        #终止条件
        if root is None:
            newNode = TreeNode(val)
            return newNode
        #单层遍历
        if root.val < val:
            root.right = self.insertIntoBST(root.right,val)
            
        if root.val > val:
            root.left = self.insertIntoBST(root.left,val)
        return root

题目并没有要求需要改变树的结构，所以只需要将节点插入叶子节点上。添加节点不需要改二叉树的结构

题目链接/文章讲解：代码随想录

视频讲解：原来这么简单？ | LeetCode：701.二叉搜索树中的插入操作_哔哩哔哩_bilibili

二刷：（未ac）

迭代无返回值方法，这种方法更直观，更容易一下子想到

var insertIntoBST = function(root, val) {
    const find = function(cur,val){
          // 如果遇到叶子节点，将值插入
        if(cur === null){
            let newNode = new TreeNode(val);
            if(pre.val > val){
                pre.left= newNode;
            }else{
                pre.right= newNode;
            }
            return ;
        }
        // 记录上一个节点为父节点
        pre = cur;
        if(val > cur.val){
            find(cur.right,val);
        }
        if(val < cur.val){
            find(cur.left,val); 
        }
    }
    if(root === null){
        return new TreeNode(val);
    }
    // 先记录当前节点为空
    let pre = null;
    find(root,val);
    return root;
};

递归法有返回值

var insertIntoBST = function(root, val) {
    const find = function(cur,val){
        // 终止条件
        if(cur === null){
            let newNode = new TreeNode(val);
            return newNode;
        }
        if(val<cur.val){
            cur.left = find(cur.left,val)
        }
        if(val>cur.val){
            cur.right = find(cur.right,val)
        }
        return cur;
    }
    if(root === null){
        return new TreeNode(val);
    }
    return find(root,val);
};

迭代法

var insertIntoBST = function(root, val) {
    // 迭代法
    if(root === null){
        return new TreeNode(val);
    }
    let cur = root;
    let pre = null;
    while(cur){
        // 移动前记录一下上一个节点的值
        pre = cur
        if(cur.val > val){
            cur = cur.left;
        }else{
            cur = cur.right;
        }
    }
    // 如果找到了
    if(pre.val > val){
        pre.left = new TreeNode(val);
    }else{
        pre.right = new TreeNode(val);
    }
    return root;
};

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

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        #终止条件
        #当没有找到删除的点
        if root is None:return None
        #当找到删除的点
        if root.val == key:
            #如果是叶子节点
            if root.left is None and root.right is None:
                return None
            #如果非叶子节点
            elif root.left is not None and root.right is None:
                return root.left
            elif root.left is None and root.right is not None:
                return root.right
            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

分两种情况：

没找到删除的点

找到了删除的点

        删除叶子节点

        删除非叶子节点

                左为空，右不为空

                左为不空，右为空

                左不空，右不空

                        最为复杂，需要满足BTS的特征，所以需要找到右子树的最大的数

中间的处理逻辑是这样的

题目链接/文章讲解：代码随想录

视频讲解：调整二叉树的结构最难！| LeetCode：450.删除二叉搜索树中的节点_哔哩哔哩_bilibili

var deleteNode = function (root, key) {
    // 终止条件
    //如果啥都没找到就返回null
    if (root === null) {
        return null;
    }
    //分五种情况
    if (root.val === key) {
        if (root.left !== null && root.right === null) {
            return root.left;
 
        } else if (root.left === null && root.right !== null) {
            return root.right;
 
        } else if (root.left === null && root.right === null) {
            //都为空
            return null;
        } else {
            let cur = root.right;
            // 找右子树的左叶子节点
            while (cur.left !== null) {
                cur = cur.left;
            }
            cur.left = root.left;
            root = root.right;
            return root;
        }
    }
    if (root.val > key) {
        root.left = deleteNode(root.left, key);
    }
    if (root.val < key) {
        root.right = deleteNode(root.right, key);
    }
    return root;
};