a guest Nov 14th, 2019 138 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.     def delNodes(self, root, to_delete):
  2.         '''
  3.        Use bottom up appraoch: if my left/right is part of delete list, I will cut my left/right branch
  4.        if I am part of delete list, I will add my left/right pointers #if exist# => return True
  5.        otherwise: return False (meaning I'm not part of delete list, don't worry about me)
  7.        P.S: if my left/right pointers were part of delete list they would have already been taken care of in my previous recurion call, that's why bottom-up approach is better and no need to track the parent pointer.
  8.        '''
  9.         if root is None:
  10.             return []
  11.         del_set=set(to_delete)
  13.         def delete(root,del_set,root_list):
  14.             if root is None:
  15.                 return False
  17.             pleft=delete(root.left,del_set,root_list)
  18.             pright=delete(root.right,del_set,root_list)
  20.             if pleft:
  21.                 root.left=None
  22.             if pright:
  23.                 root.right=None
  24.             if root.val in del_set:
  25.                 if root.left:
  26.                     root_list.append(root.left)
  27.                 if root.right:
  28.                     root_list.append(root.right)
  29.                 return True
  30.             return False
  32.         root_list=[]
  33.         if root.val not in del_set:
  34.             root_list.append(root)
  35.         delete(root,del_set,root_list)
  36.         return root_list
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!