Печать пути к узлу дерева в виде списка - PullRequest
Новая
       49

Печать пути к узлу дерева в виде списка

0 голосов
/ 28 мая 2020

Я немного схожу с ума.

Моя цель очень проста. В двоичном дереве укажите узел и верните путь к этому узлу в виде списка. Доступен ряд реализаций.

Здесь - одна из лучших и наиболее простых: 

def path(root, k):
    if not root:
        return []
    if root.val == k:
        return [root.val]
    res = path(root.left, k)
    if res:
        return [root.val] + res
    res = path(root.right, k)
    if res:
        return [root.val] + res
    return []

Из чисто образовательных соображений я решил переписать его с вспомогательная функция, в которой я передаю пустой список и рекурсивно добавляю в него элементы. 

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

    def path2Node2(self, root, node2):
        if not root:
            return None

        def _helper(root, node, paths):
            if not root:
                return []
            if root.val == node.val:
                paths.append(root.val)
                return paths
            return _helper(root.left, node, paths + [root.val])
            return _helper(root.right, node, paths + [root.val])


        return _helper(root, node2, [])


if __name__ == '__main__':
    l = TreeNode(10)
    l.left = TreeNode(8)
    l.right = TreeNode(2)
    l.left.left = TreeNode(3)
    l.left.right = TreeNode(5)
    l.right.left = TreeNode(4)
    print(l.path2Node2(l, l.left))

Он работает, если я передаю узел root ( print (l.path2Node2 (l, l) ).

Это работает, если я передаю левый дочерний элемент ( print (l.path2Node2 (l, l.left)) )

Но если я прохожу l.left.right или l.right.left, он возвращает [].

Я не могу понять это последние несколько часов. Что мне не хватает?

Ответы [ 2 ]

0 голосов
/ 28 мая 2020

Итак, вот ответ на мой собственный вопрос. 

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

    def path2Node2(self, root, node2):
        if not root:
            return []

        def _helper(root, node, paths):
            if not root:
                return []
            if root.val == node.val:
                paths.append(root.val)
                return paths
            l = _helper(root.left, node, paths + [root.val])
            r =  _helper(root.right, node, paths + [root.val])
            if l: return l
            if r: return r

        return _helper(root, node2, [])


if __name__ == '__main__':
    l = TreeNode(10)
    l.left = TreeNode(8)
    l.right = TreeNode(2)
    l.left.left = TreeNode(3)
    l.left.right = TreeNode(5)
    l.right.left = TreeNode(4)
    print(l.path2Node2(l, l.right))

Я добавил две строки: 

if l: return l
if r: return r

Но до сих пор не понимаю, в чем разница с моим исходным подходом.

0 голосов
/ 28 мая 2020

Похоже, вы решаете сегодняшнюю задачу CodeSignal. Вот мое решение Python3. Надеюсь, это поможет. 

#
# Binary trees are already defined with this interface:
# class Tree(object):
#   def __init__(self, x):
#     self.value = x
#     self.left = None
#     self.right = None
def findCommonValues(t1, t2):
    def dfs(node:Tree, vals:list, comparison:dict=None):
        """Run a depth-first search on the tree by passing the root. If comparison is passed, then it
        is used to determine if we should add the value of node to the vals list. Otherwise, always
        add value to the vals list."""
        if not node:
            return
        if node.left:
            dfs(node.left, vals, comparison)
        if comparison is None or node.value in comparison:
            vals.append(node.value)
        if node.right:
            dfs(node.right, vals, comparison)

    # Create an empty list and use it to gather all the values from the first Tree
    vals = []
    dfs(t1, vals)
    # This line coverts my list to a dict, where each item in the list is a key, and the val is 
    # arbitrary (it will just be an incremented int here). This way, we can search for previous values
    # with constant run time.
    comparison = {k: v for v, k in enumerate(vals)}
    # Reset the list and process the 2nd Tree
    vals = []
    dfs(t2, vals, comparison)
    # Now the vals list has what we're looking for, thanks to line 17 in dfs
    return vals

Для тех, кто смотрит на это в будущем, здесь - это ссылка на вызов на CodeSignal (ранее CodeFights).

...