计算二叉树中每个分支的长度并打印出遍历的节点

2024-03-29 02:20:26 发布

您现在位置:Python中文网/ 问答频道 /正文

我试图返回所有路径的长度,以及二叉树的实际路径,其值按叶节点的位置从左到右排序。你知道吗

例如,对于这个二叉树(下图),答案应该是[(3, '4‐2‐1'), (4, '8‐5‐2‐1'), (4, '9‐5‐2‐1'), (2, '7‐1')],因为叶节点的路径是“1‐2‐4”(长度3)、“1‐2‐5‐8”(长度4)、“1‐2‐5‐9”(长度4)等等

enter image description here

我尝试过使用递归(下面的示例代码)来计算路径的长度,但一直得到一个TypeError: unsupported operand type(s) for +: 'int' and 'list'。你知道吗

    res = []
    count = 0

    if T== None:
        return 0

    lengthL = 1 + self._pathV2(T.leftT)
    lengthR = 1+ self._pathV2(T.rightT)

    count = lengthR + lengthL
    res.append(count)

任何帮助解决这个问题将不胜感激!你知道吗


Tags: 答案代码self路径示例节点排序count
1条回答
网友
1楼 · 发布于 2024-03-29 02:20:26

因为您没有提供完整的代码,所以我无法使用您的代码创建一个编码示例。你知道吗

我通过修改https://www.geeksforgeeks.org/given-a-binary-tree-print-out-all-of-its-root-to-leaf-paths-one-per-line/中的代码创建了一个编码示例,如下所示。你知道吗

class Node: 

    # A binary tree node has data, 
    # pointer to left child and a  
    # pointer to right child 
    def __init__(self, data): 
        self.data = data 
        self.right = None
        self.left = None

def dfs_paths(stack, root, paths = []): 
    """ Depth first search through the tree for paths ensures paths are ordered 
        by the position of the leaf nodes from left to right """

    if root == None: 
        return

    # append this node to the path array 
    stack.append(root.data) 
    if(root.left == None and root.right == None): 

        # append all of its  
        # root - to - leaf 
        paths.append(' '.join([str(i) for i in stack[::-1]]))

    # otherwise try both subtrees 
    dfs_paths(stack, root.left, paths) 
    dfs_paths(stack, root.right, paths) 
    stack.pop() 

def paths_with_counts(root):
    """ Add counts to paths """
    paths = []
    dfs_paths([], root, paths)  # depth first search for paths

    # Add count to paths i.e. ('4-2-1') => (3, '4-2-1')
    return list(map(lambda p: (len(p.split()), p), paths))

用法示例

生成树示例

root = Node(1); 
root.left = Node(2); 
root.right = Node(7);
root.left.left = Node(4)
root.left.right = Node(5)
root.left.right.left = Node(8)
root.left.right.right = Node(9)

print(paths_with_counts(root))

输出

[(3, '4 2 1'), (4, '8 5 2 1'), (4, '9 5 2 1'), (2, '7 1')]

相关问题 更多 >