代码随想录day22【二叉树】二叉树的最近公共祖先 二叉搜索树的最近公共祖先 二叉搜索树中的插入操作 删除二叉搜索树中的节点

二叉树的最近公共祖先

力扣题目

var lowestCommonAncestor = function(root, p, q) {
    if(!root) return root
    if(root ==p || root ===q) return root

    let left=lowestCommonAncestor(root.left,p,q)
    let right=lowestCommonAncestor(root.right,p,q)

    if(left && right) {
        return root
    }else if(!left && right) {
        return right
    }else  if(left && !right) {
        return left
    }else if(!left && !right){
        return null
    }
};

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

力扣题目
关键：怎样才是最近的公共祖先
思路：
1.判断左右子树是否有值，有则向上返回

var lowestCommonAncestor = function(root, p, q) {
    if(!root) return null
    if(root.val >p.val && root.val>q.val){
        let left=lowestCommonAncestor(root.left,p,q)
        if(left) return left
    }else if(root.val <p.val && root.val<q.val){
        let right=lowestCommonAncestor(root.right,p,q)
        if(right) return right
    }
    return root
};
//迭代法待补充

二叉搜索树中的插入操作

力扣题目
思路：每个元素都可以在叶子结点上找到插入新节点的位置

var insertIntoBST = function(root, val) {
    if(!root) {
        let newNode = new TreeNode(val)
        return newNode
    }

    if(root.val >val){
        root.left=insertIntoBST(root.left,val)
        return root

    }else{
        root.right=insertIntoBST(root.right,val)
        return root
    }
};

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

力扣题目
分析：
1.需要挪动结点的位置
2.四种删除结点的情况:删除结点的左右子结点是否为空;当左右子结点均不为空时，根据二叉搜索树的特性，将左结点的孩子，作为右子结点的左孩子。
3.删除结点的逻辑放在终止条件中。用递归的效果来实现删除结点

var deleteNode = function(root, key) {
    if(!root) return root

    if(root.val ===key){
        if(!root.left && !root.right){
            return null
        }else if(!root.left && root.right){
            return root.right
        }else if(root.left && !root.right){
            return root.left
        }else{
            let cur = root.right
            while(cur.left){
                cur =cur.left
            }
            cur.left = root.left
            return root.right
        }
    }

    if (key > root.val) {
        root.right = deleteNode(root.right, key);
        return root;
    } else if (key < root.val) {
        root.left = deleteNode(root.left, key);
        return root;
    }
};