Day 22 | 235.二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点

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

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

初始思路

236是二叉树的最近公共祖先，也可以用到这题。这题可以利用二叉搜索树的特性减少一些查询。

代码

var lowestCommonAncestor = function (root, p, q) {
    if (!root) return root
    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
    } else {
        // 当前节点的值在给定值的中间，就是最深的祖先
        return root
    }
};

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
}

感想

1. 二叉树是有序的，因为所有节点的值都不同，且p q值不同。其实只要从上到下遍历的时候，cur节点是数值在[p, q]区间中则说明该节点cur就是最近公共祖先了。
2. 而且因为二叉树有序，就不需要回溯，直接往下找就行了。

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

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

初始思路

在不改变原BST的结构上，将val挂载在这颗树上。

代码

var insertIntoBST = function(root, val) {
    const setInOrder = (root, val) => {
        if (!root) {
            let node = new TreeNode(val)
            return node
        }
        if (root.val > val) {
            root.left = setInOrder(root.left, val)
        } else if (root.val < val) {
            root.right = setInOrder(root.right, val)
        }
        return root
    }
    return setInOrder(root, val)
};

var insertIntoBST = function (root, val) {
    if (!root) {
        root = new TreeNode(val)
    } else {
        // 找到val的父节点
        let parent = new TreeNode(0)
        let cur = root
        while (cur) {
            parent = cur
            if (cur.val > val) cur = cur.left
            else cur = cur.right
        }
        let node = new TreeNode(val)
        // 将node节点挂载在父节点上
        if (parent.val > val) parent.left = node
        else parent.right = node
    }
    return root
}

感想

1. 题目说有多种答案，其实就是改变了原BST的结构，可以不改变，只是遵循原结构的基础上新增一个节点。
2. 还是递归容易想出来。

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

题目：450.删除二叉搜索树中的节点 讲解：https://www.bilibili.com/video/BV1tP41177us

初始思路

删除节点需要改变BST的结构

代码

var deleteNode = function (root, key) {
    if (!root) return null
    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
    } else {
        // 情况一：左右都为空，是叶子节点
        if (root.left == null && root.right == null) {
            return null
        }
        // 情况二：左右节点其中一个不存在，直接让父节点指向子节点即可
        if (root.left !== null && root.right == null) {
            return root.left
        } else if (root.left == null && root.right !== null) {
            return root.right
        }
        // 情况三：左右节点都不为空，将右子树中最小的节点补位
        const rightNode = root.right
        // 获取右子树中最左侧的节点
        const minNode = getMinNode(rightNode)
        // 将待删除的节点的值更换
        root.val = minNode.val
        // 删除最小值节点
        root.right = deleteNode(root.right, minNode.val)
        return root
    }
};
function getMinNode (root) {
    while (root.left) {
        root = root.left
    }
    return root
}

var deleteNode = function (root, key) {
    const deleteOneNode = target => {
        if (!target) return target
        if (!target.right) return target.left
        let cur = target.right
        while (cur.left) {
            cur = cur.left
        }
        cur.left = target.left
        return target.right
    }
    if (!root) return root
    let cur = root
    let pre = null
    while (cur) {
        if (cur.val === key) break
        pre = cur
        cur.val > key ? cur = cur.left : cur = cur.right
    }
    if (!pre) {
        return deleteOneNode(cur)
    }
    if (pre.left && pre.left.val === key) {
        pre.left = deleteOneNode(cur)
    }
    if (pre.right && pre.right.val === key) {
        pre.right = deleteOneNode(cur)
    }
    return root
}

感想

1. 没找到删除的节点：遍历到空节点直接返回
2. 左右孩子都为空（叶子节点）：直接删除该节点，返回null为根节点
3. 左孩子为空，右孩子不为空：删除节点，右孩子补位，返回右孩子为根节点
4. 右孩子为空，左孩子不为空：删除节点，左孩子补位，返回左孩子为根节点
5. 左右孩子均不为空：删除节点，将右子树中最小的值补位，返回删除后的root节点为根节点