Недавно мне пришлось научить старшеклассников программировать. Существует не так много учебных пособий, удобных для начинающих, по алгоритмам, закодированным на JavaScript, на каком языке они изучали. Потому я решил сделать один.

В этой статье я постараюсь объяснить некоторые основные алгоритмы, которые вы должны изучить перед интервью с кодировкой.

Если вы не знакомы с концепцией двоичного дерева, я рекомендую просмотреть страницу Википедии. Если вы полностью овладеете этими основными алгоритмами, вам будет легче решать более сложные проблемы.

Что такое двоичное дерево поиска (BST)?

BST, обычно встречающийся в интервью с кодированием, является древовидной структурой данных с одним корнем в верхней части. Они являются отличным способом хранения числовых значений, поскольку их упорядоченная природа позволяет производить быстрый поиск и поиск.

По сравнению с обычным деревом, BST обладает следующими свойствами:

• каждый левый дочерний имеет меньшее значение, чем его отец
• каждый правильный ребенок имеет большую ценность, чем его отец
• каждый узел может содержать от 0 до 2 детей.

Следующая диаграмма должна кое-что прояснить вещи.

Определение узла бинарного дерева

Обычно мы определяем узел двоичного дерева с такой функцией в Javascript:

 function TreeNode(val, left, right) {
     this.val = val
     this.left = left
     this.right = right
 }

Основные обходы бинарного дерева (Inorder, Postorder, Preorder)

Первое, что нужно знать, – это прокрутить каждый узел BST. Это позволяет выполнять функцию на всех узлах нашего BST. Например, если мы хотим найти значение x В нашем BST нам понадобятся узлы.

Есть три основных способа сделать это. К счастью, у них общие темы.

Порядковый обход

Рекурсивный алгоритм – это самый простой способ начать работу с обходом бинарного дерева в порядке. Идея такова:

• Если узел нулевой, ничего не делайте – иначе рекурсивно вызывайте функцию из левого дочернего узла.
• Затем выполните некоторые операции с узлом после обхода, хотя все дочерние левые элементы. Наш текущий узел гарантированно будет самым левым узлом.
• Наконец вызовите функцию на node.right.

Алгоритм Inorder обходит узлы дерева слева, к середине, справа.

/**
* @param {TreeNode} root
*/
const inorder = (root) => {
    const nodes = []
    if (root) {
        inorder(root.left)
        nodes.push(root.val)
        inorder(root.right)
    }
    return nodes
}
// for our example tree, this returns [1,2,3,4,5,6]

Постордер обход

Рекурсивный алгоритм – это самый простой способ начать работу с постордерным обходом.

• Если узел нулевой, ничего не делайте – иначе рекурсивно вызывайте функцию из левого дочернего узла.
• Когда левых детей больше не будет, вызовите функцию node.right.
• Наконец выполните некоторые операции с узлом.

Обход Postorder посещает узлы дерева слева, справа, внутрь.

/**
* @param {TreeNode} root
*/
const postorder = (root) => {
    const nodes = []
    if (root) {
        postorder(root.left)
        postorder(root.right)
        nodes.push(root.val)
    }
    return nodes
}
// for our example tree, this returns [1,3,2,6,5,4]

Обход предварительного заказа

Рекурсивный алгоритм – это самый простой способ начать работу с обходом предварительного заказа.

• Если узел нулевой, ничего не делайте – иначе выполните какую-нибудь операцию с узлом.
• Перейдите к левому дочернему узлу и повторите.
• Выделите правый дочерний узел и повторите.

Обход Postorder посещает узлы дерева изнутри, слева, справа.

/**
* @param {TreeNode} root
*/
const preorder = (root) => {
    const nodes = []
    if (root) {
        nodes.push(root.val)
        preorder(root.left)
        preorder(root.right)
    }
    return nodes
}
// for our example tree, this returns [4,2,1,3,5,6]

Что такое двоичное дерево поиска?

Действительное дерево двоичного поиска (BST) имеет ВСЕХ левых дочерних со значениями меньше родительского узла и ВСЕХ правых дочерних элементов со значениями больше родительского узла.

Чтобы проверить, является ли дерево действительным деревом двоичного поиска:

• Определите минимальное и максимальное значение, которое может иметь текущий узел
• Если значение узла выходит за пределы этих границ, верните значение false
• Рекурсивно проверьте левые дочерние элементы узла, при этом максимальное ограничение установлено на значение узла
• Рекурсивно проверьте верные дочерние элементы узла, при этом минимальная привязка устанавливается на значение узла

/**
* @param {TreeNode} root
*/
const isValidBST = (root) => {
    const helper = (node, min, max) => {
        if (!node) return true
        if (node.val <= min || node.val >= max) return false
        return helper(node.left, min, node.val) && helper(node.right, node.val, max)
    }
    return helper(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER)
}

Как найти максимальную глубину двоичного дерева

Здесь алгоритм пытается найти высоту/глубину нашего BST. Другими словами, мы смотрим, сколько «уровней» содержит BST.

• Если нулевой узел, мы возвращаем 0, поскольку он не добавляет глубины
• В противном случае мы добавляем +1 к нашей текущей глубине (мы прошли один уровень)
• Рекурсивно вычислить глубину дочерних узлов и вернуть максимальную сумму между node.left и node.right

/**
* @param {TreeNode} root
*/
const maxDepth = function(root) {
    const calc = (node) => {
        if (!node) return 0
        return Math.max(1 + calc(node.left), 1 + calc(node.right))
    }
    return calc(root)
};

Как найти самого низкого общего предка между двумя узлами дерева

Давайте повысим сложность. Как найти общего предка между двумя узлами дерева в нашем бинарном дереве? Давайте рассмотрим несколько примеров.

В этом дереве самым низким общим предком 3 и 1 является 2. LCA 3 и 2 равно 2. LCA 6 и 1 и 6 равно 4.

Видите здесь шаблон? LCA между двумя узлами дерева является либо одним из самих узлов (случай 3 и 2), либо родительским узлом, где первый дочерний узел находится где-то в его левом поддеревье, а второй дочерний – где-то в его правом поддеревье.

Алгоритм поиска самого низкого общего предка (LCA) между двумя узлами дерева p и q выглядит следующим образом:

• Проверьте, найдено ли p или q в левом или правом поддеревьях.
• Затем проверьте, есть ли текущий узел p или q
• Если одно из p или q найдено в левом или правом поддеревье, а одно из p или q является самим узлом, мы нашли LCA
• Если в левом или правом поддеревье находятся оба p и q, мы обнаружили LCA

/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
*/
const lowestCommonAncestor = function(root, p, q) {
    let lca = null
    const isCommonPath = (node) => {
        if (!node) return false
        var isLeft = isCommonPath(node.left)
        var isRight = isCommonPath(node.right)
        var isMid = node == p || node == q
        if (isMid && isLeft || isMid && isRight || isLeft && isRight) {
            lca = node
        }
        return isLeft || isRight || isMid
    }
    isCommonPath(root)
    return lca
};

Подведению

Подытоживая, мы научились обходить, проверять и вычислять глубину BST.

Об этих алгоритмах часто спрашивают в интервью с кодировкой. Важно понять их, прежде чем применять более продвинутые программы BST, например поиск LCA двух узлов.