二叉樹每一片葉子的路徑

上面的函式 AllPaths()將一個包含二叉樹每個葉子路徑的陣列附加到全域陣列中 res。

代碼作業得很好，但我想洗掉全域變數 res并使函式回傳一個陣列。我怎樣才能做到這一點？

class Node:
    def __init__(self, value, left=None, right=None) -> None:
        self.value = value
        self.left  = left
        self.right = right

res = []
def allPaths(node, arr=[]):
    if node:
        tmp = [*arr, node.value]
        if not node.left and not node.right: # Leaf
            res.append(tmp)
        allPaths(node.left, tmp)
        allPaths(node.right, tmp)


root             = Node(1)
root.left        = Node(2);
root.left.left   = Node(4);
root.left.right  = Node(5);
root.right       = Node(3);
root.right.right = Node(6);
"""
          1         <-- root
        /   \
       2     3  
     /   \    \
    4     5    6    <-- leaves
"""
allPaths(root)
print(res)
# Output : [[1, 2, 4], [1, 2, 5], [1, 3, 6]]

uj5u.com熱心網友回復：

一種讓您完全避免使用內部串列和全域串列的簡單方法是制作一個生成器來生成值。然后你可以把它傳遞給list最終結果：

class Node:
    def __init__(self, value, left=None, right=None) -> None:
        self.value = value
        self.left  = left
        self.right = right

def allPaths(node):  
    if node:
        if not node.left and not node.right: # Leaf
            yield [node.value]
        else:
            yield from ([node.value]   arr for arr in allPaths(node.left))
            yield from ([node.value]   arr for arr in allPaths(node.right))
              
root             = Node(1)
root.left        = Node(2);
root.left.left   = Node(4);
root.left.right  = Node(5);
root.right       = Node(3);
root.right.right = Node(6);
        
g = allPaths(root)
list(g)

# [[1, 2, 4], [1, 2, 5], [1, 3, 6]]

uj5u.com熱心網友回復：

一種方法是通過回溯來實作：

def allPaths(node, partial_res, res):
    if not node: 
        return
    if not node.left and not node.right:
        res.append(partial_res[:]   [node.value])
        return    
    partial_res.append(node.value)
    allPaths(node.left, partial_res, res)
    allPaths(node.right, partial_res, res)
    partial_res.pop()

res = []
allPaths(root, [], res)
print(res)

uj5u.com熱心網友回復：

您可以在遞回中傳遞當前路徑：

def allPaths(node,path=[]):
    if not node: return            # no node, do nothing
    if node.left or node.right:    # node is not a leaf, recurse down      
        yield from allPaths(node.left,path [node.value])  # left leaves if any
        yield from allPaths(node.right,path [node.value]) # right leaves if any
    else:
        yield path [node.value]    # leaf node, return full path

uj5u.com熱心網友回復：

我提供另一種選擇。

def allPaths(root, path=[]):
    tmp = []
    if root.left:
        tmp.extend(allPaths(root.left, path   [root.value]))
    if root.right:
        tmp.extend(allPaths(root.right, path   [root.value]))
    if not root.left and not root.right:
        tmp.append(path   [root.value])
    return tmp


tree = allPaths(root)
print(tree)

輸出是：

[[1, 2, 4], [1, 2, 5], [1, 3, 6]]

標籤：Python 算法 树 二叉树

上一篇：獲得串列第一個單值的最佳方法

下一篇：兩個Numpy陣列matplotlib的折線圖