In [1]:
1
2
3
import random
from binarytree import build, tree, bst, heap, Node
plot = lambda x: build(a).pprint()
Build Binary Tree
Binary tree library
In [2]:
1
2
3
4
size = 4
root = tree(height=size, is_perfect=False)
print("A={}, |A|={}".format(root.values, len(root.values)))
root.pprint()
1
2
3
4
5
6
7
8
9
10
11
12
13
A=[28, 30, 25, 24, 0, 13, 14, 20, 23, 26, 18, 10, 21, 4, 8, 7, None, 2, None, None, 11, 9, 3, None, None, None, 29, None, 16, 12], |A|=30
________________28____________
/ \
______30______ _______25_____
/ \ / \
_24__ ____0__ _13 ___14___
/ \ / \ / \ / \
20 23 26 18 10 21 4 _8
/ / \ / \ \ \ /
7 2 11 9 3 29 16 12
In [3]:
1
2
A = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14]
build(A).pprint() # use binary tree libray
1
2
3
4
5
6
7
8
9
10
____________1__________
/ \
__2_____ ____3____
/ \ / \
4 _-99_ _-99 _7
/ \ / \ / \ / \
8 9 -99 -99 12 13 -99 14
Build binary tree for Leetcode problems.
If I solve a problem related to binary tree in leetcode,
the representatation of binary tree is somewhat different.
I will show you as follows.
(If a internal node is null, it makes error when indexing).
In [4]:
1
2
3
null = None
A = [1,2,3,4,null,null,7,8,9,null,14]
# build(A).pprint() # Error!
Therefore I implemented it by referring to StefanPochmann ‘s post
In [5]:
1
2
3
4
5
6
7
8
9
10
def buildtree(A):
if not A: return None
nodes = [None if x == None else Node(x) for x in A]
kids = nodes[::-1]
root = kids.pop()
for node in nodes:
if node:
if kids: node.left = kids.pop()
if kids: node.right = kids.pop()
return root
In [6]:
1
2
print(A)
buildtree(A).pprint()
1
2
3
4
5
6
7
8
9
10
11
[1, 2, 3, 4, None, None, 7, 8, 9, None, 14]
1
/ \
__2 3
/ \
4 7
/ \ \
8 9 14
In [7]:
1
buildtree([5,4,8,11,null,17,4,7,null,null,null,5]).pprint()
1
2
3
4
5
6
7
8
9
10
5___
/ \
_4 _8__
/ / \
11 17 4
/ /
7 5
Reference
[1] binary tree library in python
[2] StefanPochmann
‘s post
Leave a comment