迭代/遍历BST Python

Question

我试图在BST的特定范围内找到并求和**所有数字。我只访问了树顶下的两个数字。如何访问所有其他号码。当尝试迭代或遍历时，我收到错误。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
output = 0

if  root.left.val >= low and root.left.val <= high:
output += root.left.val
if  root.right.val >= low and root.right.val <= high:
output += root.right.val
return output

Answer 1

必须使用递归函数:

def sum_tree(root, low, high):
value = root.value
if value < low or value > high:
value = 0
if root.left == None and root.right == None:
return value
if root.left == None:
return value + sum_tree(root.right, low, high)
if root.right == None:
return value + sum_tree(root.left, low, high)
return value + sum_tree(root.left, low, high) + sum_tree(root.right, low, high)

例子:

nodes =[5, 6, 6,7, 2, 10, 5, None, 4, 13]
binary_tree = binarytree.build(nodes)
print(binary_tree)
print("Sum min-max:",sum_tree(binary_tree, 5, 10))

结果:

_____5___
/         
__6___       _6
/           /  
7       _2   10   5
     /
4   13
Sum min-max: 39

Answer 2

正如@nokla所说，理想情况下，您需要使用递归方法来实现这一点。下面是递归方法的一个变体，它非常有效:

class Solution:
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
_sum = 0
def traverse(n):
nonlocal _sum
if n:
if low <= n.val <= high:
_sum += n.val
traverse(n.left)
traverse(n.right)
traverse(root)
return _sum