Получить глубину узла в двоичном дереве, используя итеративную DFS? - PullRequest
Новая
       37

Получить глубину узла в двоичном дереве, используя итеративную DFS?

0 голосов
/ 16 марта 2019

При использовании рекурсивной DFS для дерева можно получить глубину любого узла, передав глубину в качестве параметра рекурсивной функции. Однако с нерекурсивной DFS я не знаю, как получить глубину узла.

У меня есть базовая настройка шаблона DFS, но я не могу понять, что изменить, чтобы вернуть глубину целевого узла. 

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def dfs(root, val):
    stack = [root]
    while stack:
        node = stack.pop()
        if node.val == val:
            return node
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)

Я нашел это решение: Глубина дерева с использованием DFS , но, похоже, он использует другой способ хранения дерева, а также требуется предварительное знание всего дерева.

...