Sum levels 明智的二叉树

Question

我必须为二叉树中的每个级别实现求和我必须 return 一个包含位置 i 的列表，第 i 个总和例子：如果我有这棵树

      24
    /   \
   14    27
  / \  /  \
11  20 12  55

我必须return[24,41,98]

我尝试在 python

中实施此解决方案

def sommaperlivelli(p, lista):
if p == None:
    return 
if p.left != None and p.right != None:
    lista.append(p.left.key + p.right.key)
sommaperlivelli(p.left, lista)
sommaperlivelli(p.right, lista)
return lista

我只能得到第一个和，不能加根。我该怎么做？

这是我用的class

class NodoABR:
def __init__(self, key = None, left = None, right = None, parent = None):
    self.key = key
    self.left = left
    self.right = right
    self.parent = parent

这就是我向树中添加节点的方式

def inserisciNodo(p, n):
if p == None:
    return NodoABR(n)
else:
    if p.key == n:
        return p
    elif p.key < n:
        rchild = inserisciNodo(p.right, n)
        p.right = rchild
        rchild.parent = p
    else:
       lchild = inserisciNodo(p.left, n)
       p.left = lchild
       lchild.parent = p 
return p

这是一个二叉搜索树在主要功能中我这样做

p = NodoABR(24)
p = inserisciNodo(p, 14)
p = inserisciNodo(p, 27)
p = inserisciNodo(p, 11)
p = inserisciNodo(p, 20)
p = inserisciNodo(p, 12)
p = inserisciNodo(p, 55)
print(sommaperlivelli(p,[]))

Answer 1

假设您有类似的树节点 class，您可以尝试此操作并进行修改以满足您的特定需求。

from collections import deque

class Node:     # TreeNode eg.
    def  __init__(self, key):
        self.data = key
        self.left = None
        self.right = None
    
def LevelSum(root):
    answer = []
    
    if (root == None):  return 0        # base case

    result = root.data
    
    # track of # nodes at every level when traversal, and sum them up
    q = deque()
    q.append(root)
    
    while len(q):             #  > 0):
        size = len(q)

    # Iterate for all the nodes
        tot = 0   
         
        while size:      # meaning --- size > 0 
        # Dequeue an node from queue
            tmp = q.popleft()

        # Add this node's value to current sum.
            tot += tmp.data

        # Enqueue left and right children of dequeued node
            if (tmp.left != None):  q.append(tmp.left)
                
            if (tmp.right != None): q.append(tmp.right)
            
            size -= 1
        print(tot, result)

        answer.append(tot)
        
    return answer

示例：

if __name__ == '__main__':
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    root.right.right = Node(6)
    root.right.right.left = Node(9)
    root.right.right.right = Node(11)
    """
    # Constructed Binary tree is:
    #          1
    #        /  \
    #        2   3                 #  5
    #       / \   \
    #      4 5     6               # 15
    #             / \
    #             9   11           # 20
    """
    print("level sum is", LevelSum(root))

[编辑] PO作者想学习另一种方法。（非队列）

from collections import Counter
from typing import List


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


def level_sum(root: Node) -> int:
    
    def dfs(node, level):
        if not node: return
        
        total[level] += node.data
        dfs(node.left,level  + 1)
        dfs(node.right,level + 1)
        
    total = Counter()
    dfs(root, 1)

    print(total)     # showing each level & its total  --- can be commented out 
    
    return total.most_common()[0][1]    # the largest total

Answer 2

使用你的 NodoABR class，这是一个简单的树遍历，深度优先，我们在每次迭代时记下级别，并用它来存储节点值，arr 是列表的数组（或列表），每个级别一个：

# Create sample tree
root = NodoABR(24, NodoABR(14, NodoABR(11), NodoABR(20)), NodoABR(27, NodoABR(12), NodoABR(55)))

def handle_node(nd, level):
    # Add a new level list if needed
    if len(arr) == level:
        arr.append([])
    # Append this node value to its proper level list
    arr[level].append(nd.key)

    # Recurse, increasing the level
    if nd.left is not None:
        handle_node(nd.left, level+1)
    if nd.right is not None:
        handle_node(nd.right, level+1)

# Main program
arr = []
handle_node(root, 0)
print(arr)

这是输出：

[[24], [14, 27], [11, 20, 12, 55]]

Sum levels 明智的二叉树

Sum levels wise binary tree

python

tree