在二叉树中转换嵌套列表的列表 [英] Converting a list of nested lists in binary tree

问题描述

在python中，我有一个表示二叉树的嵌套列表的列表:

In python, I have a list of nested lists that represents a binary tree:

L = [0, [[1, [2, 3]], [4, [5, 6]]]]

所以树可以看如下:

        0
       /  \
      1    4
     /\    /\ 
    2  3  5  6

我现在想实现一个函数，该函数将树的一个级别作为输入并返回该级别的所有节点:

I now want to implement a function that takes as input a level of the tree and returns all the nodes of that level:

GetNodes(0) = 0
GetNodes(1) = [1,4]
GetNodes(2) = [2,3,5,6]

是否有一种简便的方法来避免对L的所有嵌套列表进行残酷搜索? 是否有可能在python中对二进制树进行更标准的管理，也许将我的列表列表转换为其他内容?

Is there an easy way to do this, avoiding a brutal search on all the nested lists of L? Is there the possibility of a more standard management of binary trees in python, maybe converting my list of lists in something else?

推荐答案

我会去参加BFS.将尽快发布代码:)

I would go for a BFS. Will post code asap :)

在这里

L = [0, [[1, [2, 3]], [4, [5, 6]]]]


def getLevel(k, tree):
    currentLevel = [tree[0]]
    nextLevel = tree[1]
    level = 1
    while level <= k:
        _currentLevel = []
        _nextLevel = []
        for subtree in nextLevel:
            if isinstance(subtree, list):
                _currentLevel.append(subtree[0])
                if isinstance(subtree[1], list):
                    _nextLevel.append(subtree[1])
                else:
                    _currentLevel.append(subtree[1])
            else:
                _currentLevel.append(subtree)
        currentLevel= _currentLevel
        nextLevel = _nextLevel
        level+=1
    return currentLevel



print getLevel(0, L)
print getLevel(1, L)
print getLevel(2, L)

这篇关于在二叉树中转换嵌套列表的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！