本文共 935 字，大约阅读时间需要 3 分钟。

非递归树搜索与范围和计算

题目详情：

给定二叉搜索树的根结点root，计算属于区间[low, high]之间的所有结点的值的和。

解题思路：

理解题意的关键是区分节点值是否落在给定范围内，而不是节点是否在范围内。正确的做法是递归地遍历树的左和右子树，并检查每个节点的值是否在给定范围[low, high]内。边界值的处理至关重要，必须确保这些条件被正确评估。

代码实现：

这是一个使用先序遍历的递归方法。具体来说，首先递归访问左子树，并将结果添加到总和中。然后检查根节点是否在范围内。如果是，则将其值加到结果中。接着递归访问右子树并累加结果。这种方法确保了所有符合条件的节点都会被正确计算。

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    def rangeSumBST(self, root, low, high):
        res = 0
        if not root:
            return res
        res += self.rangeSumBST(root.left, low, high)
        if low <= root.val <= high:
            res += root.val
        res += self.rangeSumBST(root.right, low, high)
        return res

知识点：

了解二叉树的基本结构及其应用。掌握递归算法的编写方法及其在数据处理中的优势。通过实际应用案例加深对二叉树遍历的理解，这将帮助您在面对类似问题时能够更高效地解决问题。

这种方法确保了所有符合要求的节点都会被正确访问并记录，性能出色且逻辑清晰。是的，二叉树仍然在许多实际应用中发挥重要作用，深入理解其结构和遍历方法非常有必要。

转载地址：http://acagz.baihongyu.com/