代码随想录Day22-Leetcode235. 二叉搜索树的最近公共祖先，701.二叉搜索树中的插入操作，450.删除二叉搜索树中的节点

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

题目链接:https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
又玩了一天,手又生疏了好多;
这道题看了题解,先用公共解法了,之前的题没刷,就给现在留坑了

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
 //递归:搜索左子树,搜索右子树,若都搜索到结果即使自己(暂时不考虑自身)
 //暂且不考虑二叉搜索树性质
var lowestCommonAncestor = function(root, p, q) {
    if(root == null||root == p||root == q){
        return root
    }
    let lResult = lowestCommonAncestor(root.left,p,q)
    let rResult = lowestCommonAncestor(root.right,p,q)
    if(lResult !=null&&rResult!=null){
        return root
    }else if(lResult!=null){
        return lResult
    }else if(rResult!=null){
        return rResult
    }
    else{
        return null
    }
};
//犯错:审题出错,把,p,q当成值而非结点;

看了文章后,发现可以直接利用性质,第一个到区间中央的就是了
虽然,后面看了文章代码后发现只用遍历一条边就够了,还是不够高效

var lowestCommonAncestor = function(root, p, q) {
    if(root == null){
        return root
    }
    if(root.val>=Math.min(p.val,q.val)&&root.val<=Math.max(p.val,q.val)){
        return root
    }
    let lResult = lowestCommonAncestor(root.left,p,q)
    if(lResult!=null){
        return lResult
    }
    let rResult = lowestCommonAncestor(root.right,p,q)
    if(rResult!=null){
        return rResult
    }
    
    return null
};

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

题目链接:https://leetcode.cn/problems/insert-into-a-binary-search-tree/
递归是很显然的,小于,插不进去就插左子树,大于同理

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var insertIntoBST = function(root, val) {
    if(root == null){
        return new TreeNode(val)
    }
    if(val>root.val){
        if(root.right==null){
            root.right = new TreeNode(val)
        }else{
            insertIntoBST(root.right,val)
        }
    }else{
        if(root.left == null){
            root.left = new TreeNode(val)
        }else{
            insertIntoBST(root.left,val)
        }
    }
    return root
};
//错误:经典递归忘参数

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

题目链接:https://leetcode.cn/problems/delete-node-in-a-bst
这个看了题解
没想到可以把左子树直接接到右子树的最左边
递归返回根节点引用也很巧妙

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
 //看了题解,五种情况:
 //没找到
 //左右孩子为空:直接删
 //左/右孩子为空,用那一个取代
 //左右孩子都不为空:将左孩子放在右孩子的最左面节点的左孩子上
var deleteNode = function(root, key) {
    if(root == null){
        return null
    }
    if(key == root.val){
        if(root.left==null){
            return root.right
        }else if(root.right == null){
            return root.left
        }else{
            let p  = root.right;
            while(p.left!=null){
                p = p.left
            }
            p.left = root.left
            return root.right
        }
    }else{
        root.left = deleteNode(root.left,key)
        root.right = deleteNode(root.right,key)
    }
    return root
};