Построить дерево с заданным обходом предварительного заказа - PullRequest
Новая
       14

Построить дерево с заданным обходом предварительного заказа

6 голосов
/ 05 февраля 2011

Дается специальный тип дерева, где все листья отмечены L, а другие отмечены N.Каждый узел может иметь 0 или максимум 2 узла.Дается предварительный обход дерева.

Дайте алгоритм построения дерева из этого обхода.

Ответы [ 2 ]

16 голосов
/ 05 февраля 2011

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

Preorder(T)
  if (T is not null)
    print T.label
    Preorder(T.left)
    Preorder(T.right)

Попробуем найти алгоритм для ввода NNLLNL.

Очевидно, что этикетка корня печатается первой. Итак, вы знаете, что корень имеет метку N. Теперь алгоритм возвращается на левое поддерево. Это также N в зависимости от ввода. Рекурсируйте на левом поддереве того, что L. Теперь вы должны отказаться, потому что вы достигли листа. Следующая позиция на входе также L, поэтому у текущего узла есть правый дочерний элемент, помеченный L. Отступить один раз. Снова вернитесь назад, потому что вы добавили все дочерние элементы текущего узла (максимум 2 дочерних элемента). Теперь вы снова в корне. Вы должны идти направо, потому что вы уже пошли налево. Согласно данным, это N. Таким образом, правым потомком корня является N. Левый ребенок этого будет L. Это ваше дерево: 

       N
     /   \
    N     N
   / \   /
  L   L L

Обратите внимание, что решение не обязательно уникально, но это даст вам возможное решение.

псевдокод: 

k = 0
input = ... get preorder traversal vector from user ...
Reconstruct(T)
  if input[k] == N
    T = new node with label N
    k = k + 1 
    Reconstruct(T.left)
    Reconstruct(T.right)
  else 
    T = new node with label L
    T.left = T.right = null
    k = k + 1

Вызов с нулевым узлом.

Последующий вопрос : учитывая как предварительный порядок, так и обход по порядку бинарного дерева, содержащего различные метки узлов, как можно уникальным образом восстановить дерево?

0 голосов
/ 04 июля 2019

Вот моя версия golang, которая использовалась для решения многих проблем с деревом в leetcode. 

// NewPreorderTree returns preorder tree relate to nums, nums must has not Ambiguity.
// -1 in nums represents child is null.
//
// Example 1:
//  Input: [1, 2, 3]
//  Generate:
//          1
//         /
//        2
//       /
//      3
//
// Example 2:
//  Input: [1, 2, -1, -1, 3] or [1, 2, -1, -1, 3, -1, -1]
//  Generate:
//         1
//        / \
//       2   3
func NewPreorderTree(nums ...int) *TreeNode {
    return (&preorderTree{nums}).constructTree()
}

type preorderTree struct {
    nums []int
}

func (p *preorderTree) constructTree() *TreeNode {
    if len(p.nums) == 0 {
        return nil
    }

    if p.nums[0] == -1 {
        p.nums = p.nums[1:]
        return nil
    }

    root := &TreeNode{Val: p.nums[0]}
    p.nums = p.nums[1:]
    root.Left = p.constructTree()
    root.Right = p.constructTree()
    return root
}
...