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

更新於：2020年10月6日

826 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告