Binary Tree

105. Construct Binary Tree from Preorder and Inorder Traversal

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