Advertisement
Iam_Sandeep

Count pairs from two BSTs whose sum is equal to a given value x

Apr 17th, 2022
971
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.80 KB | None | 0 0
  1. class Solution:
  2.     def countPairs(self, root1, root2, x):
  3.         cur1,cur2=root1,root2
  4.         st1,st2=deque(),deque()
  5.         count=0
  6.         while True:
  7.             while cur1:
  8.                 st1.append(cur1)
  9.                 cur1=cur1.left
  10.             while cur2:
  11.                 st2.append(cur2)
  12.                 cur2=cur2.right
  13.             if not st1 or not st2:
  14.                 break
  15.             top1,top2=st1[-1],st2[-1]
  16.             sum=top1.data+top2.data
  17.             if sum<x:
  18.                 st1.pop()
  19.                 cur1=top1.right
  20.             elif sum>x:
  21.                 st2.pop()
  22.                 cur2=top2.left
  23.             else:
  24.                 count+=1
  25.                 st1.pop()
  26.                 st2.pop()
  27.                 cur1,cur2=top1.right,top2.left
  28.         return count
  29.  
  30.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement