Using dfs to solve this problem with detail comment


  • 0
    C

    The main idea is to build a balanced tree first and set the value of the nodes when traversing the tree with inorder traversing. Inorder traversal a binary search tree output a ascending list. So we use inorder to set the tree nodes correctly.

    # @param root, a tree node
    # @param head, a list node
    # @return a list node
    def buildTreeWithSortedList(self, root, head):
    	if not root.left and not root.right:
    		root.val = head.val
    		return head.next
    	
    	if root.left:
    		head = self.buildTreeWithSortedList(root.left, head)
    
    	root.val = head.val
    	head = head.next
    
    	if root.right:
    		head = self.buildTreeWithSortedList(root.right, head)
    
    	return head
    		
    # @param head, a list node
    # @return a tree node
    def sortedListToBST(self, head):
    	if not head: return None
    
    	#step1. build tree using a queue.
    	root = TreeNode(0)
    	queue = [root]
    	count = 1
    	l = head.next
    	while l:
    		cur = queue.pop(0)
    		if l:
    			cur.left = TreeNode(0)
    			queue.append(cur.left)
    			l = l.next
    		if l:
    			cur.right = TreeNode(0)
    			queue.append(cur.right)
    			l = l.next
    
    	#step2. use DFS to set the value of each tree node
    	self.buildTreeWithSortedList(root, head)
    	return root

Log in to reply
 

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