代码随想录训练营Day22 | 235.二叉搜索树的最近公共祖先

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

思路

• 如果当前节点值在 [p,q] 或者 [q,p] 之间，那么该节点即为 p、q的最近公共祖先。
• 由于二叉搜索树具有排序特征，所以无需遍历整棵二叉树，可以在遍历过程中指定方向。

var lowestCommonAncestor = function(root, p, q) {
    let left = null
    let right = null
    const travelTree = (root, p, q) => {
        if (!root) {
            return
        }
        // 搜索一边
        if (root.val > p.val && root.val > q.val) {
            left = travelTree(root.left, p, q)
            if (left !== null) {
                return left
            }
        }
        if (root.val < p.val && root.val < q.val) {
            right = travelTree(root.right, p, q)
            if (right !== null) {
                return right
            }
        }
        return root
    }
    return travelTree(root, p, q)
};

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

思路

• 按照二叉树的规则遍历，遇到空节点插入新的节点即可

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