Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # Time: O(N) where n the number of nodes in the input tree, as each node is checked once.
- # Space: O(N)
- '''
- V = 5
- 4
- / \x
- 2 6
- x/ \
- 5 7
- 4
- / \
- 2 5
- 6
- \
- 7
- 1) if root.val <= 4, continue to split root.right (left, right )
- 1. root.right = left
- 2. return root, right
- 2) else: continue to split root.left
- 1. by the same logic
- 2.
- '''
- # Definition for a binary tree node.
- # class TreeNode(object):
- # def __init__(self, x):
- # self.val = x
- # self.left = None
- # self.right = None
- class Solution(object):
- def splitBST(self, root, V):
- """
- :type root: TreeNode
- :type V: int
- :rtype: List[TreeNode]
- """
- if not root:
- return None, None
- elif root.val <= V:
- left, right = self.splitBST(root.right, V)
- root.right = left
- return root, right
- else:
- left, right = self.splitBST(root.left, V)
- root.left = right
- return left, root
Add Comment
Please, Sign In to add comment