Skip to content

二叉搜索树.md

Latest commit

 

History

History
115 lines (94 loc) · 3.36 KB

二叉搜索树.md

File metadata and controls

115 lines (94 loc) · 3.36 KB
Raw

二叉搜索树

定义

  • 每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。
  • 每个节点中的值必须小于（或等于）存储在其右子树中的任何值。

应用

98. 验证二叉搜索树
function isValidBST(root: TreeNode | null): boolean {
    return helper(root, -Infinity, Infinity)
};

function helper(node: TreeNode | null, lower: number, upper: number): boolean {
    if (node === null) {
        return true
    }
    if (node.val <= lower || node.val >= upper) {
        return false
    }
    return helper(node.left, lower, node.val) && helper(node.right, node.val, upper)
}
701. 二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。

function insertIntoBST(root: TreeNode | null, val: number): TreeNode | null {
    if (root === null) {
        return new TreeNode(val)
    }
    if (root.val > val) {
        root.left = insertIntoBST(root.left, val)
    } else {
        root.right = insertIntoBST(root.right, val)
    }
    return root
};
450. 删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

思路：秒懂就完事了

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
    if (root === null) {
        return root
    }
    if (root.val < key) {
        root.right = deleteNode(root.right, key)
    } else if (root.val > key) {
        root.left = deleteNode(root.left, key)
    } else {
        if (root.left === null) {
            return root.right
        } else if (root.right === null) {
            return root.left
        } else {
            let cur: TreeNode = root.right
            while (cur.left !== null) {
                cur = cur.left
            }
            cur.left = root.left
            return root.right
        }
    }
    return root
};
110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

const isBalanced = function (root) {
    if (maxDepth(root) === -1) {
        return false
    }
    return true
};

const maxDepth = function (root) {
    if (root === null) {
        return 0
    }
    const left = maxDepth(root.left)
    const right = maxDepth(root.right)
    if (left === -1 || right === -1 || Math.abs(right - left) > 1) {
        return -1
    }
    if (left > right) {
        return left + 1
    } else {
        return right + 1
    }
}

练习