Summary of Common Algorithms of python Binary Tree
- 2021-12-04 19:02:55
- OfStack
Directory 1.1 Initialization of 2-tree 1.2 Create a 2-tree 1.3 Preorder traversal 1.4 Middle order traversal 1.5 Post order traversal 1.6 Sequence traversal 1.7 Count node number 1.8 Calculate tree depth 1.9 Calculate tree leaf tree 1.10 Obtain K layer node number 1.11 Judge whether two 2-trees are identical 1.12 Mirror image of 2-tree 1.13 Find the lowest common ancestor node 1.14 Get the distance between two nodes 1.15 Find all ancestor nodes of one node
Initialization of 1.1 2 Fork Tree
#initial of BinaryTree
class BinaryTree:
def __init__(self,rootObj):
self.val = rootObj
self.left = None
self.right = None
def insertLeft(self,newNode):
if self.left == None:
self.left = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.left = self.left
self.left = t
def insertRight(self,newNode):
if self.right == None:
self.right = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.right = self.right
self.right = t
1.2 Create a 2-tree
#create a BinaryTree [18,7,11,3,4,5,6,#,#,#,#,1,3,2,4]
# 18
# 7 11
#3 4 5 6
# 1 3 2 4
root = BinaryTree(18)
root.left = BinaryTree(7)
root.right = BinaryTree(11)
root.left.left = BinaryTree(3)
root.left.right = BinaryTree(4)
root.right.left = BinaryTree(5)
root.right.right = BinaryTree(6)
root.right.left.left = BinaryTree(1)
root.right.left.right = BinaryTree(3)
root.right.right.left = BinaryTree(2)
root.right.right.right = BinaryTree(4)
1.3 Preorder traversal
# Recursive version
def PreOrder(self, node):
if node:
print(node.val)
self.PreOrder(node.left)
self.PreOrder(node.right)
# Circular version
def PreOrderLoop(self, node):
if node == None:
return
stack =[]
print(node.val)
stack.append(node)
node = node.left
while stack!=[] or node:
while node:
print(node.val)
stack.append(node)
node = node.left
node = stack[-1].right
stack.pop()
#ouput: 18 7 3 4 11 5 1 3 6 2 4
1.4 Ordered traversal
# Recursive version
def InOrder(self, node):
if node:
self.InOrder(node.left)
print(node.val)
self.InOrder(node.right)
# Circular version
def InOrderLoop(self, node):
if node == None:
return None
stack = []
stack.append(node)
node = node.left
while stack!=[] or node:
while node:
stack.append(node)
node = node.left
print(stack[-1].val)
node = stack[-1].right
stack.pop()
#output : 3 7 4 18 1 5 3 11 2 6 4
1.5 Post-order traversal
# Recursion
def PostOrder(self, node):
if node:
self.PostOrder(node.left)
self.PostOrder(node.right)
print(node.val)
# Non-recursive
def PostOrderLoop(self, node):
if node == None:
return
stack =[]
stack.append(node)
pre = None
while stack!=[]:
node = stack[-1]
if ((node.left==None and node.right==None) or
(pre and (pre == node.left or pre ==node.right))):
print(node.val)
pre = node
stack.pop()
else:
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
#output:3 4 7 1 3 5 2 4 6 11 18
1.6 Sequence traversal
def LevelOrder(self, node):
if node == None:
return
stack = []
stack.append(node)
while stack!=[]:
node = stack[0]
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
print(node.val)
stack.pop(0)
output: 18 7 11 3 4 5 6 1 3 2 4
1.7 Count the number of nodes
# Recursive version
def CountNode(self, root):
if root == None:
return 0
return self.CountNode(root.left) + self.CountNode(root.right) + 1
# Non-recursive version
def CountNodeNotRev(self, root):
if root == None:
return 0
stack = []
stack.append(root)
index = 0
while index<len(stack):
if stack[index].left:
stack.append(stack[index].left)
if stack[index].right:
stack.append(stack[index].right)
index += 1
print(len(stack))
output: 11
1.8 Calculate the Depth of the Tree
def getTreeDepth(self, root):
if root == None:
return 0
left = self.getTreeDepth(root.left) + 1
right = self.getTreeDepth(root.right) + 1
return left if left>right else right
1.9 Calculate the Leaf Tree of the Tree
def countLeaves(self, root):
if root == None:
return 0
if root.left==None and root.right==None:
return 1
return self.countLeaves(root.left)+self.countLeaves(root.right)
1.10 Get the number of K layer nodes
def getKLevel(self, root, K):
if root == None: return 0
if K == 1: return 1
return self.getKLevel(root.left, K-1)+self.getKLevel(root.right, K-1)
1.11 Determine whether two binary trees are the same
#create a BinaryTree [18,7,11,3,4,5,6,#,#,#,#,1,3,2,4]
# 18
# 7 11
#3 4 5 6
# 1 3 2 4
root = BinaryTree(18)
root.left = BinaryTree(7)
root.right = BinaryTree(11)
root.left.left = BinaryTree(3)
root.left.right = BinaryTree(4)
root.right.left = BinaryTree(5)
root.right.right = BinaryTree(6)
root.right.left.left = BinaryTree(1)
root.right.left.right = BinaryTree(3)
root.right.right.left = BinaryTree(2)
root.right.right.right = BinaryTree(4)
1.12 Mirroring of a 2-tree
#create a BinaryTree [18,7,11,3,4,5,6,#,#,#,#,1,3,2,4]
# 18
# 7 11
#3 4 5 6
# 1 3 2 4
root = BinaryTree(18)
root.left = BinaryTree(7)
root.right = BinaryTree(11)
root.left.left = BinaryTree(3)
root.left.right = BinaryTree(4)
root.right.left = BinaryTree(5)
root.right.right = BinaryTree(6)
root.right.left.left = BinaryTree(1)
root.right.left.right = BinaryTree(3)
root.right.right.left = BinaryTree(2)
root.right.right.right = BinaryTree(4)
1.13 Find the lowest common ancestor node
#create a BinaryTree [18,7,11,3,4,5,6,#,#,#,#,1,3,2,4]
# 18
# 7 11
#3 4 5 6
# 1 3 2 4
root = BinaryTree(18)
root.left = BinaryTree(7)
root.right = BinaryTree(11)
root.left.left = BinaryTree(3)
root.left.right = BinaryTree(4)
root.right.left = BinaryTree(5)
root.right.right = BinaryTree(6)
root.right.left.left = BinaryTree(1)
root.right.left.right = BinaryTree(3)
root.right.right.left = BinaryTree(2)
root.right.right.right = BinaryTree(4)
1.14 Get the distance between two nodes
def getDist(self, root, node1, node2):
lca = self.findLCA(root, node1, node2) # Find the lowest common ancestor node
level1 = self.FindLevel(lca, node1) # Distance from ancestor node to two nodes
level2 = self.FindLevel(lca, node2)
return level1+level2
def FindLevel(self, node, target):
if node == None: return -1
if node == target: return 0
level = self.FindLevel(node.left, target)
if level == -1: level = self.FindLevel(node.right, target)
if level != -1: return level + 1
return -1
1.15 Find all ancestral nodes of a node
#create a BinaryTree [18,7,11,3,4,5,6,#,#,#,#,1,3,2,4]
# 18
# 7 11
#3 4 5 6
# 1 3 2 4
root = BinaryTree(18)
root.left = BinaryTree(7)
root.right = BinaryTree(11)
root.left.left = BinaryTree(3)
root.left.right = BinaryTree(4)
root.right.left = BinaryTree(5)
root.right.right = BinaryTree(6)
root.right.left.left = BinaryTree(1)
root.right.left.right = BinaryTree(3)
root.right.right.left = BinaryTree(2)
root.right.right.right = BinaryTree(4)