Реализация DFS для поиска маршрута между двумя узлами дерева - PullRequest
Новая
       50

Реализация DFS для поиска маршрута между двумя узлами дерева

0 голосов
/ 11 марта 2020 
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def getDFSpath(root,goal,stack):
    stack.append(root.val)
    if root.left is None and root.right is None and root.val != goal:
        stack.pop()
        return []
    elif root.val == goal:
        return stack
    else:
        leftstack = getDFSpath(root.left,goal,stack)
        rightstack = getDFSpath(root.right,goal,stack)
        if len(leftstack) == 0 and len(rightstack) > 0:
            return rightstack
        elif len(rightstack) == 0 and len(leftstack) > 0:
            return leftstack
        else:
            return []

one = TreeNode(1)
two =TreeNode(2)
three =TreeNode(3)
four = TreeNode(4)
five =TreeNode(5)
six =TreeNode(6)
seven =TreeNode(7)
eight = TreeNode(8)
nine =TreeNode(9)
ten = TreeNode(10)
eleven = TreeNode(11)

one.left = two
one.right = three
two.left = four
two.right = five
three.left = six
three.right = seven
four.left = ten
four.right = eleven
five.left = nine
five.right = eight
mystack = getDFSpath(one,11,[])
print(mystack)

Я не уверен, что не так с этой реализацией. Я пытаюсь найти маршрут между узлом один и целевым узлом со значением 11. Правильный ответ должен быть [1,2,4,11]. Однако возвращается: [1, 2, 4, 11, 5, 3]

1 Ответ

0 голосов
/ 14 марта 2020

Давайте посмотрим ближе на следующие строки кода: 

leftstack = getDFSpath(root.left,goal,stack)
rightstack = getDFSpath(root.right,goal,stack)

Здесь вы вызываете DFS для левого и правого узла и передаете одну и ту же переменную stack. Например, вызов DFS для левого узла находит путь (Простой пример - маршрут от 1 до 2). После этого вы вызываете DFS для правого узла (3). Чем дольше вы используете одну и ту же переменную стека, вызывая DFS для правого узла, изменит ее. Посмотрите на следующую строку: 

if root.left is None and root.right is None and root.val != goal:

Для узла 3 это не так, поэтому он не удалит 3 из стека! И вы получите [1, 2, 3] в результате. Также вы не обрабатываете случай, когда ваш узел имеет только левого или только правого потомка. Исправлен код с моими комментариями: 

def getDFSpath(root, goal, stack):
    stack.append(root.val)
    if root.val == goal:
        return stack
    else:
        leftstack = getDFSpath(root.left, goal, stack[:]) if root.left is not None else []  # if left node is missing skip it
        rightstack = getDFSpath(root.right, goal, stack[:]) if root.right is not None else []  # if right node is missing skip it
        if len(leftstack) == 0 and len(rightstack) > 0:
            return rightstack
        elif len(rightstack) == 0 and len(leftstack) > 0:
            return leftstack
        else:
            stack.pop()  # we didn't find path, remove current node from stack
            return []

Вывод:

[1, 2, 4, 11]

...