Самый низкий общий предок двоичного дерева

Средняя

20 February 2024

Описание задачи #

Вам дано двоичное дерево. Найдите наименьшего общего предка (LCA) двух заданных узлов в дереве.

Согласно определению LCA в Википедии: «Наименьший общий предок определяется между двумя узлами p и q как самый нижний узел в дереве T, который имеет как p, так и q в качестве потомков (где мы позволяем узлу быть потомком самого себя).»

Ограничения #

Количество узлов в дереве находится в диапазоне от 2 до 10⁵.
Значения каждого узла в дереве находятся в диапазоне от -10⁹ до 10⁹.
Значения всех узлов в дереве уникальны.
p != q.
p и q всегда существуют в дереве.

Примеры #

Входные параметры: дерево выше, p = 5, q = 1.

Ответ: 3

Объяснение: LCA узлов 5 и 1 равен 3.
Входные параметры: дерево выше, p = 5, q = 4.

Ответ: 5

Объяснение: LCA узлов 5 и 4 равен 5, поскольку узел может быть потомком самого себя согласно определению LCA.

Решение #

Решение этой задачи достаточно интуитивно. Сначала мы пройдем по дереву вглубь. В тот момент, когда встретится любой из узлов p или q, вернем логический флаг. Флаг помогает определить, нашли ли мы нужные узлы на каком-либо из путей. Тогда наименьшим общим предком будет узел, для которого обе рекурсии поддерева возвращают флаг true. Это также может быть узел, который сам является одним из узлов p или q и для которого одна из рекурсий поддерева возвращает флаг true.

Реализация #

Для реализации будем использовать рекурсивный подход с замыканием для хранения переменной lca.

package longest_common_ancestor_of_binary_tree

type TreeNode struct {
	Left  *TreeNode
	Right *TreeNode
	Val   int
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	var lca *TreeNode
	var findNode func(node *TreeNode) bool

	findNode = func(node *TreeNode) bool {
		if node == nil || q == nil || p == nil {
			return false
		}

		left := findNode(node.Left)
		right := findNode(node.Right)

		if left && right {
			lca = node
			return true
		}

		if node.Val == p.Val || node.Val == q.Val {
			if left || right {
				lca = node
			}
			return true
		}

		return left || right
	}

	findNode(root)

	return lca
}

export type TreeNode = {
    val: number
    left?: TreeNode
    right?: TreeNode
}

export const lowestCommonAncestor = (root?: TreeNode, p?: TreeNode, q?: TreeNode): TreeNode | null => {
    let lca: TreeNode | null = null;

    const findNode = (node?: TreeNode): boolean => {
        if (!node || !p || !q) {
            return false
        }

        const left = findNode(node.left)
        const right = findNode(node.right)

        if (left && right) {
            lca = node
            return true
        }

        if (node.val == p.val || node.val == q.val) {
            if (left || right) {
                lca = node
            }
            return true
        }

        return left || right;
    }

    findNode(root)

    return lca
}

Оценка сложности #

По времени

O(n) так как в худшем случае нам нужно посетить все n узлов в дереве.

По памяти

O(n) так как максимальный объем пространства, используемого стеком рекурсии, будет равен n.

Оригинал задачи на Leetcode

Algorithmics