A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.

[Leetcode 105] Construct Binary Tree from Preorder and Inorder Traversal

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right classSolution: defbuildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: iflen(preorder) == 0: returnNone

# get root node from preorder list rootVal = preorder[0] root = TreeNode(rootVal)

# divide inorder list to left and right subtree rootIdx = inorder.index(rootVal) leftInorder = inorder[:rootIdx] rightInorder = inorder[rootIdx + 1 :]

# find corresponding preorder left and right subtree leftPreorder = preorder[1 : len(leftInorder) + 1] rightPreorder = preorder[len(leftInorder) + 1 :]

# recursively construct left and right subtree root.left = self.buildTree(leftPreorder, leftInorder) root.right = self.buildTree(rightPreorder, rightInorder)

# return the root of tree return root

[Leetcode 106] Construct Binary Tree from Inorder and Postorder Traversal

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right classSolution: defbuildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]: # check if empty tree list iflen(inorder) == 0: returnNone

# find the root in postorder list and construct the root node rootVal = postorder[-1] root = TreeNode(rootVal)

# divide the inorder list to left and right subtree rootIdx = inorder.index(rootVal) leftInorder = inorder[:rootIdx] rightInorder = inorder[rootIdx + 1 :]

# recursively construct left and right subtree root.left = self.buildTree(leftInorder, leftPostorder) root.right = self.buildTree(rightInorder, rightPostorder)

# return the root of tree return root

[Leetcode 226] Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root.

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right from collections import deque