Using dfs to solve this problem with detail comment

  • 0

    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
    	if root.left:
    		head = self.buildTreeWithSortedList(root.left, head)
    	root.val = head.val
    	head =
    	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 =
    	while l:
    		cur = queue.pop(0)
    		if l:
    			cur.left = TreeNode(0)
    			l =
    		if l:
    			cur.right = TreeNode(0)
    			l =
    	#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.