如何遍历二叉搜索树（BST）求指定范围[low,high]的节点值总和？

你的代码存在三个核心问题：

• 仅处理了根节点的直接左右子节点，未遍历整棵树的所有节点
• 未判断root.left/root.right是否为None，直接访问.val会引发AttributeError
• 没有利用二叉搜索树（BST）的特性优化遍历逻辑，做了无意义的节点访问

递归解法（利用BST特性剪枝） #

递归是处理树结构最直观的方式，结合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:
        if not root:
            return 0
        # 当前节点值小于low，只需要遍历右子树
        if root.val < low:
            return self.rangeSumBST(root.right, low, high)
        # 当前节点值大于high，只需要遍历左子树
        if root.val > high:
            return self.rangeSumBST(root.left, low, high)
        # 当前节点在范围内，累加当前值+左右子树符合条件的和
        return root.val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)

迭代解法（栈实现，避免递归栈溢出） #

如果树的深度很大，递归可能引发栈溢出，这时可以用栈实现迭代遍历，同样结合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:
        if not root:
            return 0
        total = 0
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                if low <= node.val <= high:
                    total += node.val
                # 节点值大于low，左子树可能存在符合条件的节点
                if node.val > low:
                    stack.append(node.left)
                # 节点值小于high，右子树可能存在符合条件的节点
                if node.val < high:
                    stack.append(node.right)
        return total

内容的提问来源于stack exchange，提问作者Nikoi Nikoi