The basic concept of binary tree

First, a binary tree is a tree , A tree is a data structure , By n A set of nodes . Due to the various properties of binary trees , Our commonly used tree is a binary tree , A binary tree is degree by 2 The tree of . The number of subtrees a node has is called the degree of the node , For a tree , The degree of the tree is in the degree of all nodes , The biggest degree .
Depth of tree ： The number of tree layers
leaf node （ Terminal node ）： Degree is 0 The node of
Full binary tree ： Only the last layer has leaf nodes , And the degree of the penultimate node is 2.

The picture is from the Internet , Infringement and deletion .
Perfect binary tree ： Only the degree of the last and penultimate nodes is less than 2. And the nodes of the last layer are arranged continuously from the left .

Properties of binary trees ：

1. The first i The maximum number of nodes on the layer is 2^i-1.
2. Depth is k The maximum number of binary tree nodes of is 2^k-1.
3. contain n The depth of a binary tree of nodes is at least log₂(n+1).
4. The number of leaf nodes is equal to the degree 2 The number of knots +1.

123 The three properties are interrelated , Write down the number 1 Nature ,23 The nature is not difficult , Here we mainly talk about Chapter 4 Nature .
Because the degree of the node of the binary tree is not greater than 2, Then you can get the equation 1：
Total number of nodes n = 0 The number of degree nodes n0 + 1 The number of degree nodes n1 + 2 The number of degree nodes n2
namely n = n0 + n1 + n2 ------------- type (1)
because 0 Degree node has no child node ,1 I have a child ,2 I have two children , And only the root node is not the child of other nodes , Sum up points equal to child knot points + Number of root nodes （ If it's difficult to understand, take the picture above , Do it yourself ）, So we can get the equation 2：
n = n1 + 2*n2 + 1 --------------- type (2)
By the type 1 Sum formula 2 Available ,n0 = n2 + 1.

After having a basic concept of binary tree , Next, let's talk about the very important traversal of binary trees , There are four ways to traverse binary trees ： The former sequence traversal , In the sequence traversal , Post sequence traversal and sequence traversal . The first, middle and last traversal can be understood as the order of traversing the parent node , The preamble is to traverse the parent node first, and then the left and right nodes , The middle order is first left, then father, then right , The next order is to traverse the left and right nodes first , Finally, traverse the parent node , All three traversal methods need to be used Stack , It can be implemented recursively or iteratively , Recursion uses the system stack , Iterations use self maintained stacks , Iterate faster , The following two templates will implement these two methods respectively . Sequence traversal is from top to bottom , Traverse all nodes from left to right , Sequence traversal uses BFS Methods , Yes queue .

Pictured above is an example ,
The result of preorder traversal ：[1 2 4 8 9 5 10 2 6 7]
The result of middle order traversal ：[8 4 9 2 10 5 1 6 2 7]
The result of subsequent traversal ：[8 9 4 10 5 2 6 2 7 1]
The result of sequence traversal ：[[1], [2 2], [4 5 6 7], [8 9 10]]
The question on the force button ：
144. Preorder traversal of two tree
94. Middle order traversal of binary trees
145. Postorder traversal of binary trees
101. Sequence traversal of binary tree
python Definition of tree node ：

class TreeNode:
	def __init__(sefl, x):
		self.val = x
		self.left = None
		self.right = None

Recursive method template

Recursion is very simple .

The former sequence traversal

def preorderTraversal(root):
	if not root:
		return []
	return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

In the sequence traversal

def inorderTraversal(root):
	if not root:
		return []
	return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

After the sequence traversal

def postorderTraversal(root):
	if not root:
		return []
	return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]

Iterative method template

Next is the most important part . There are several implementation methods of iterative method , In order to unify the template , Let's add the tag WHITE and BLACK, White means not being visited , Black means you have visited . If the current node is a new node , Just stack the node , Set as accessed (BALCK), And stack its left and right child nodes , Set to not accessed (WHITE); If the current node has been accessed , Directly add the result . Use this template , Just change the stacking order , You can complete the first, middle and last three traversal methods .

The former sequence traversal

def preorderTraversal(root):
	WHITE, BLACK = 0, 1
	stack = [(WHITE, root)]
	res = []
	
	while stack:
		mask, cur= stack.pop()
		
		#  If the pushed node is empty , skip 
		if not cur: continue
		
		#  If the pushed node is a new node , Stack the node and set it as accessed , And stack its left and right child nodes , Set to not accessed 
		#  If the node has been accessed , Add directly to the result 
		if mask == WHITE：
			#  Because the stack is first in then out , So the stack order should be reversed 
			stack.append((WHITE, cur.right))
			stack.append((WHITE, cur.left))
			stack.append((BLACK, cur))
		else:
			res.append(cur.val)
	return res

In the sequence traversal

def inorderTraversal(root):
	WHITE, BLACK = 0, 1
	stack = [(WHITE, root)]
	res = []
	
	while stack:
		mask, cur= stack.pop()
		
		#  If the pushed node is empty , skip 
		if not cur: continue
		
		#  If the pushed node is a new node , Stack the node and set it as accessed , And stack its left and right child nodes , Set to not accessed 
		#  If the node has been accessed , Add directly to the result 
		if mask == WHITE：
			#  Because the stack is first in then out , So the stack order should be reversed 
			stack.append((WHITE, cur.right))
			stack.append((BLACK, cur))
			stack.append((WHITE, cur.left))
		else:
			res.append(cur.val)
	return res

After the sequence traversal

def postorderTraversal(root):
	WHITE, BLACK = 0, 1
	stack = [(WHITE, root)]
	res = []
	
	while stack:
		#  First in, then out 
		mask, cur= stack.pop()
		
		#  If the pushed node is empty , skip 
		if not cur: continue
		
		#  If the pushed node is a new node , Stack the node and set it as accessed , And stack its left and right child nodes , Set to not accessed 
		#  If the node has been accessed , Add directly to the result 
		if mask == WHITE：
			#  Because the stack is first in then out , So the stack order should be reversed 
			stack.append((BLACK, cur))
			stack.append((WHITE, cur.right))
			stack.append((WHITE, cur.left))
		else:
			res.append(cur.val)
	return res

You can see three traversals. Just change the stack pressing order , I can only say , Wonderful .
Reference resources ： Color marking

Sequence traversal （BFS）

I think it's better to understand , There are two requirements , The first is to put the results in a list after sequence traversal , The second is to put the results of each layer in a list , Then put these lists together to form a two-dimensional list .

Pictured above is an example , The result of the first sequence traversal is [1 2 2 4 5 6 7 8 9 10], The result of the second sequence traversal is [[1], [2 2], [4 5 6 7], [8 9 10]].
First look at the first one , Is to use the plain breadth first algorithm （BFS）：

def levelOrder(root):
	if not root:
		return []
	queue = [root]
	res = []

	while queue:
		#  First in, first out 
		cur = queue.pop(0)
		res.append(cur.val)
		if cur.left:
			queue.append(cur.left)
		if cur.right:
			queue.append(cur.right)
	return res

The second kind of sequence traversal , As long as tiered storage is based on the first ：

def levelOrder(root):
	if not root:
		return []
	queue = [root]
	res = []

	while queue:
		#  Hierarchical storage 
		level = []
		length = len(queue)
		for i in range(length):
			#  First in, first out 
			cur = queue.pop(0)
			level.append(cur.val)
			if cur.left:
				queue.append(cur.left)
			if cur.right:
				queue.append(cur.right)

		#  After traversing one layer, it will be added to the final result 
		res.append(level)
	return res

Sum up , Traversal of binary tree involves queues , Stack , recursive , iteration , Breadth first algorithm (BFS), Depth-first algorithm (DFS) Such as knowledge , After understanding, it will be of great help to do the following algorithm problems .