Reconstruct Binary Search Tree from Binary Tree


  • 0
    1

    Given a Binary Tree each node of which contains an integer, reconstruct a Binary Search Tree from the integers of the input Binary Tree, the reconstructed Binary Search Tree should be in the same shape as the input Binary Tree.

    class Node:
    	"""docstring for Node"""
    	def __init__(self, val = None):
    		self.val = val
    		self.left = None
    		self.right = None
    
    def dfs(root, res, size):
    	if root == None:
    		return 0
    	else:
    		res.append(root.val)
    	lsize = dfs(root.left, res, size)
    	rsize = dfs(root.right, res, size)
    	size[root] = (lsize, rsize)
    	return 1 + lsize + rsize
    
    def construct(nums, root, size):
    	lsize, rsize = size[root]
    	newRoot = Node(nums[lsize])
    	if lsize != 0:
    		newRoot.left = construct(nums[:lsize], root.left, size)
    	if rsize != 0:
    		newRoot.right = construct(nums[lsize + 1:], root.right, size)
    	return newRoot
    
    def convert(root):
    	res = []
    	size = {}
    	dfs(root, res, size)
    	res.sort()
    	return construct(res, root, size)
    
    root = Node(1)
    root.right = Node(0)
    # root.left = Node(2)
    newRoot = convert(root)
    print(newRoot.val, newRoot.left.val if newRoot.left else None, newRoot.right.val if newRoot.right else None)
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.