if we have a tree given below:
1
/\
2 3
/\/\
4 5 6 7
Как найти путь между узлами 4-5 или 4-6? Я знаю, как найти путь от корня до заданного узла, но не между двумя случайными узлами.Как найти путь между двумя данными узлами в двоичном дереве
вы можете взять два пути от корня к двум узлам и удалить общий подпуть.
1
/
2
/
3
/ \
4 7
/\ /\
5 6 8 9
e.g. для пути от 5 до 9 в примере вы получите два пути: 1 2 3 4 5 и 1 2 3 7 9 и найдете 3 как самый низкий общий родительский узел. затем обратный путь, начиная с 5 до общего предка, и добавьте остальные в пути к 9: 5 4 + 3 + 7 9 ->5 4 3 7 9
Что делать, если это не двоичное дерево, а нормальное дерево, а не числовые значения в нем, а некоторые цвета, как красное черное дерево? @BeyelerStudios –
@ShefaliChaudhary такой же подход, если вы можете искать корневой путь – BeyelerStudios
, но он не работает в случае, если у нас есть дерево, где корневой узел черный, и каждый черный узел имеет красный ребенок и каждый красный У узла есть черный ребенок, и если нам не нужно найти ни одного черного узла с 4-го по 5-й узел, тогда трудно найти общий путь для других узлов, а также 3 и 4. @ BeyelerStudios –
Если вы задаете вопрос о алгоритмах, то помечать как таковые (и ни C ни C++ - соответствующие теги). В противном случае вы обычно должны только тегировать язык, который вы компилируете, так как C и C++ могут быть очень разными, когда спрашивают о деталях реализации. – crashmstr
мои сообщения отвечали на ваш вопрос? можете ли вы подробно остановиться на том, где вы были удалены иначе? разместите некоторый код, чтобы показать, что вы уже пробовали, особенно, как вы идентифицируете свои узлы (как вы находите корневой путь). – BeyelerStudios
найти LCA и вычислить путь от LCA к обоим узлам –