Binary tree in Python

Posted on Edited on In , Views:

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.

Example 1:

1
2
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2:

1
2
Input: preorder = [-1], inorder = [-1]
Output: [-1]

Constraints:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder and inorder consist of unique values.
  • Each value of inorder also appears in preorder.
  • preorder is guaranteed to be the preorder traversal of the tree.
  • inorder is guaranteed to be the inorder traversal of the tree.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 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
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if len(preorder) == 0:
            return None

        # 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.

Example 1:

1
2
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Example 2:

1
2
Input: inorder = [-1], postorder = [-1]
Output: [-1]

Constraints:

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorder and postorder consist of unique values.
  • Each value of postorder also appears in inorder.
  • inorder is guaranteed to be the inorder traversal of the tree.
  • postorder is guaranteed to be the postorder traversal of the tree.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 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
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        # check if empty tree list
        if len(inorder) == 0:
            return None

        # 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 :]

        # find corresponding postorder list
        leftPostorder = postorder[: len(leftInorder)]
        rightPostorder = postorder[
            len(leftInorder) : len(leftInorder) + len(rightInorder)
        ]

        # 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 129] Sum Root to Leaf Numbers

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.
Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

Example 1:

1
2
3
4
5
6
7
8
9
10
      1
    /   \
   2     3

Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • 0 <= Node.val <= 9
  • The depth of the tree will not exceed 10.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 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
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        self.total = 0
        self.sumNumbersHelper(root, 0)
        return self.total

    def sumNumbersHelper(self, root, pathSum):
        if not root:
            return 

        # accumulate the path sum
        pathSum = pathSum * 10 + root.val

        if not root.left and not root.right:
            # add path sum to result
            self.total += pathSum

        else:
            # search left subtree
            self.sumNumbersHelper(root.left, pathSum)

            # search right subtree
            self.sumNumbersHelper(root.right, pathSum)

[Leetcode 226] Invert Binary Tree

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

Example 1:

1
2
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

1
2
Input: root = [2,1,3]
Output: [2,3,1]

Example 3:

1
2
Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# 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

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root == None:
            return root

        qu = deque()
        qu.append(root)
        while len(qu) > 0:
            node = qu.popleft()
            node.left, node.right = node.right, node.left
            if node.left != None:
                qu.append(node.left)
            if node.right != None:
                qu.append(node.right)

        return root
    def invertTree_recursive(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root == None:
            return root

        root.left, root.right = root.right, root.left

        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

    def invertTree_preorder(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root == None:
            return root

        st = []
        st.append(root)
        while len(st) > 0:
            node = st.pop()
            node.left, node.right = node.right, node.left

            if node.left != None:
                st.append(node.left)
            if node.right != None:
                st.append(node.right)

        return root