Python에서 범위의 노드 수를 찾는 프로그램

BST가 있고 왼쪽 및 오른쪽 경계 l과 r이 있다고 가정하면 루트에서 값이 l과 r(포함) 사이에 있는 모든 노드의 수를 찾아야 합니다.

따라서 입력이 다음과 같으면

l =7, r =13, 8, 10, 12의 세 노드가 있으므로 출력은 3이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따르겠습니다-

• stack :=스택이고 처음에 루트 삽입, count :=0

• 스택이 비어 있지 않은 동안 수행

  • node :=스택의 최상위 요소, 팝 요소

  • 노드가 null이 아니면

    • l <=노드의 데이터 <=r이면

      • 개수 :=개수 + 1

      • 스택 :=노드의 오른쪽과 노드의 왼쪽을 스택으로 푸시

    • 그렇지 않으면 노드의 데이터가

      • stack :=노드의 오른쪽을 스택으로 푸시

      • 그렇지 않으면

      • stack :=노드의 왼쪽을 스택으로 푸시

• 반환 횟수

예

from collections import dequeclass TreeNode:def __init__(self, data, left =None, right =None):self.data =data self.left =left self.right =rightclass 솔루션:def solve(self, root, l , r):스택, 개수 =[루트], 0 while 스택:node =stack.pop() if node:if l <=node.data <=r:count +=1 stack +=[node.right, node .left] elif node.data  
입력
 
루트 =TreeNode(12)root.left =TreeNode(8)root.right =TreeNode(15)root.left.left =TreeNode(3)root.left.right =TreeNode(10)7,13 
출력
 
3