HTML CSS JAVASCRIPT JQUERY AI PHP SQL EXCEL LINUX C# C++ C PYTHON JAVA 教程库 参考手册 技术文章 测验 练习 HOWTO FAQ

用 Python 编写程序来查找某个范围内的节点数

pythonserver side programmingprogramming更新于 2026/1/11 6:04:17

假设我们有一个 BST，并且我们还有左边界和右边界 l 和 r，我们必须找到 root 中所有节点的数量，这些节点的值位于 l 和 r 之间(含 l 和 r)。

因此，如果输入如下

l = 7，r = 13，则输出将为 3，因为有三个节点:8、10、12。

为了解决这个问题，我们将遵循以下步骤−

  • stack := a stack 并插入 root首先，count := 0

  • 当 stack 不为空时，执行

    • node := stack 顶部元素，弹出元素

    • 如果 node 不为空，则

      • 如果 l <= node 数据 <= r，则

        • count := count + 1

        • stack := 将节点右侧和节点左侧推送到堆栈

      • 否则，当 node 数据 < l，则

        • stack := 将节点右侧推入堆栈

        • 否则，

        • stack := 将节点左侧推入堆栈

  • 返回 count

示例

from collections import deque
class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, root, l, r):
      stack, count = [root], 0
      while stack:
         node = stack.pop()
         if node:
            if l <= node.data <= r:
               count += 1
               stack += [node.right, node.left]
            elif node.data < l:
               stack += [node.right]
            else: stack += [node.left]
      return count
ob = Solution()
root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)
print(ob.solve(root, 7,13))

输入

root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)
7,13

输出

3

相关文章

有用资源

打印 下一节:用 Python 编写程序，查找包含一个唯一字符的字符串总数 ❯❮ 上一节:用 Python 编写程序，查找给定数字中 1 位的数量