Binary Tree

solution 1: naive recursion

Key observations:

the first node of preorder is the root node

find the index of root from inorder list, then left part will be the left subtree and right part will be the right subtree.

For the preorder subtrees, if nodes in the left part of the inorder subtree, it is a left preorder subtree. Else, it is a right preorder subtree.

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
def helper(inorder, preorder):
if not inorder:return None
root = preorder[0]
idx = inorder.index(root)
left_inorder, right_inorder = inorder[:idx], inorder[idx+1:]
left_preorder, right_preorder= [], []
left_inorder_set = set(left_inorder)
for node in preorder[1:]:
if node in left_inorder_set:
left_preorder.append(node)
else:
right_preorder.append(node)
left = helper(left_inorder, left_preorder)
right = helper(right_inorder, right_preorder)
root_node = TreeNode(root)
root_node.left = left
root_node.right = right
return root_node
return helper(inorder, preorder)

Solution 2: from https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/34579/Python-short-recursive-solution.

def buildTree(self, preorder, inorder):
if inorder:
ind = inorder.index(preorder.pop(0))
root = TreeNode(inorder[ind])
root.left = self.buildTree(preorder, inorder[0:ind])
root.right = self.buildTree(preorder, inorder[ind+1:])
return root

Or using the below code to get rid of pop(0)

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
def helper(preorder, inorder):
if not inorder:return None
idx = inorder.index(preorder.pop())
root = TreeNode(inorder[idx])
root.left = helper(preorder, inorder[:idx])
root.right = helper(preorder, inorder[idx+1:])
return root
return helper(preorder[::-1], inorder)

101. Symmetric Tree

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if root is None:return True
def helper(node1, node2):
if node1 is None and node2 is None:return True
if node1 is None and node2 is not None:return False
if node1 is not None and node2 is None:return False
if node1.val!=node2.val:return False
return helper(node1.left,node2.right) and helper(node1.right, node2.left)
return helper(root.left, root.right)

Above code can be slightly modified to make it shorter as below

class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if root is None:return True
def helper(node1, node2):
if node1 and node2:
return node1.val==node2.val and helper(node1.left,node2.right) and helper(node1.right, node2.left)
# at lease one is None
else:return node1 == node2
return helper(root.left, root.right)

The code above is a recursive code, for the iterative code can be found here.

Link to previous binary tree article

https://medium.com/@jim.morris.shen/binary-tree-fb5c19cf338d?source=friends_link&sk=9427cbe441e4cc0d0f79c7feb54d1828

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store