Python程序：查找指定范围内的节点数量

假设我们有一个二叉搜索树 (BST)，以及左右边界l和r，我们需要找到根节点下所有值在l和r之间（包含l和r）的节点数量。

例如，

如果输入为l = 7, r = 13，则输出为3，因为存在三个节点：8、10、12。

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

• stack := 一个栈，首先插入根节点；count := 0

• 当stack非空时，执行：

  • node := 栈顶元素，并弹出该元素

  • 如果node非空，则：

    • 如果l <= node的值 <= r，则

      • count := count + 1

      • stack := 将node的右子节点和左子节点压入栈中

    • 否则，如果node的值 < l，则

      • stack := 将node的右子节点压入栈中

      • 否则，

      • stack := 将node的左子节点压入栈中

• 返回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

Arnab Chakraborty

更新于：2020年10月6日

826 次浏览

开启你的职业生涯

完成课程获得认证

开始学习