preface:
·The depth first traversal and width first traversal of binary tree are the basis for solving the problem of binary tree. Mastering the common traversal methods of binary tree can make us solve the problem of binary tree more handy.
catalogue
Recursive form of pre -, middle - and post order traversal of binary tree
Non recursive form of pre -, middle - and post order traversal of binary tree
Preorder traversal of binary tree by iteration
Post order traversal of binary tree by iteration
Middle order traversal of binary tree by iteration
The width of binary tree is traversed first
Recursive form of pre -, middle - and post order traversal of binary tree
💡: We know that in the pre -, middle -, and post order traversal of a binary tree, each node will go through three times. When we first arrive at each node, it is pre order traversal. When we arrive at each node for the second time, it is middle order traversal. When we arrive at each node for the third time, it is middle order traversal
When dealing with this node, it is post order traversal. We call this Law recursive order.
Preorder traversal: head node - left subtree - right subtree
Middle order traversal: left subtree - head node - right subtree
Post order traversal: left subtree - right subtree - head node
code:
public static class TreeNode{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val){
this.val=val;
}
}
//Preorder traversal
public static void preOrder(TreeNode root){
if(root==null){
return;
}
System.out.println(root.val);//Print when you first arrive
preOrder(root.left);
preOrder(root.right);
}
//Middle order traversal
public static void inOrder(TreeNode root){
if(root==null){
return;
}
inorder(root.left);
System.out.println(root.val);//Print the second time you come
inorder(root.right);
}
//Postorder traversal
public static void posOrder(TreeNode root){
if(root==null){
return;
}
posOrder(root.left);
posOrder(root.right);
System.out.println(root.val);//Print the third time
}Non recursive form of pre -, middle - and post order traversal of binary tree
💡: From the above, we know the concept of recursive order. In the traversal of the first, middle and last order of the binary tree, each node will come three times. How does recursion come to each node three times? The answer is that recursion makes use of the system stack. If we don't need recursion to traverse the first, middle and last order of the binary tree, we must manually press the stack to simulate the system stack.
Preorder traversal of binary tree by iteration
Idea:
🔑 Prepare a stack: design a stack to simulate the function of the system stack
The rules of stack are as follows
(1) : pop up one node at a time
(2) : there is a right child. Press the right child into the stack
(3) : a left child pushes the left child into the stack
(4) : make sure the right child first and then the left child
code:
public static class TreeNode{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val){
this.val=val;
}
}
//Press the stack yourself
//rule
//1: Pop stack top
//2: There is a right child pressing in the right child
//3: There is a left child pressing in the left child
//4: Right then left
public static void pre(TreeNode root){
if(root==null){
return;
}
Stack<TreeNode> stack=new Stack<>();
stack.add(root);
while(!stack.isEmpty()){
TreeNode cur=stack.pop();
System.out.print(cur.val+" ");
if(cur.right!=null){
stack.add(cur.right);
}
if(cur.left!=null){
stack.add(cur.left);
}
}
System.out.println();
}Post order traversal of binary tree by iteration
Idea:
💡: After learning the code of pre order traversal, we can change the pre order traversal to post order traversal through some changes.
Preorder traversal is the order of head node - left subtree - right subtree. When we use iteration to realize preorder traversal, we pop-up nodes. First press the right child and then the left child. If we press the left child and then the right child, we can get the head node right subtree
-The traversal order of the left subtree, and then reverse this order is the order of the left subtree, the right subtree and the head node.
So how do we reverse the order?
We only need to put the traversal results of the head node right subtree left subtree into another auxiliary stack in turn, and then pop up all elements from the stack in turn to get the order of the left subtree right subtree head node.
code:
public static class TreeNode{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val){
this.val=val;
}
}
public static void posOrder(TreeNode root){
if(root==null){
return;
}
Stack<TreeNode> stack=new Stack<>();
Stack<TreeNode> help=new Stack<>();
stack.add(root);
while(!stack.isEmpty()){
TreeNode cur=stack.pop();
help.add(cur);
if(cur.left!=null){
stack.add(cur.left);
}
if(cur.right!=null){
stack.add(cur.right);
}
}
while(!help.isEmpty()){
System.out.print(help.pop().val+" ");
}
System.out.println();
}Middle order traversal of binary tree by iteration
Idea:
💡: Middle order traversal is the traversal order of left subtree head node right subtree.
To ensure that each subtree is in the traversal order of the left subtree - head node - right subtree, so our traversal order is to print the node when it can no longer be left, and then go to the right tree for the same operation, that is, we press the left boundary of each subtree into the stack, pop up the node from left to no longer left, and then perform the same operation on the right subtree, This is possible because any binary tree can be completely decomposed by the left boundary.
code:
public static class TreeNode{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val){
this.val=val;
}
}
//Rule cur starts from scratch
//(1)cur!=null press cur in the stack, cur = cur Left scan left boundary
//(2)cur==null pops up the top element of the stack and prints it. cur comes to the right subtree of the pop-up element
public static void inorder(TreeNode root){
if(root==null){
return;
}
Stack<TreeNode> stack=new Stack<>();
TreeNode cur=root;
while(cur!=null||!stack.isEmpty()){
if(cur!=null){
stack.add(cur);
cur=cur.left;
}
else{
cur=stack.pop();
System.out.print(cur.val+" ");
cur=cur.right;
}
}
System.out.println();
}
The width of binary tree is traversed first
Idea:
💡: The classical implementation of width first traversal of binary tree (also known as sequence traversal) is realized through queue. The use rule of queue is to pop up a node from the queue, press the right child if there is a right child, and press the left child if there is a left child. In this way, the next layer can be pressed into the queue after each layer traverses.
code:
//Methodology: prepare a queue: when traversing each layer, let the nodes of the next layer enter the queue
//Rule 1: pop up one node from the queue at a time
//2: If there is a left child, put the left child in the queue
//3: If there are children, let the right child enter the queue
class TreeNode{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val){
this.val=val;
}
}
public static void bfs(TreeNode head){
if(head==null){
return;
}
Queue<TreeNode> queue=new LinkedList<>();
queue.add(head);
while(!queue.isEmpty()){
TreeNode cur=queue.poll();
System.out.println(cur.val);
if(cur.left!=null){
queue.add(cur.left);
}
if(cur.right!=null){
queue.add(cur.right);
}
}
System.out.println();
}As my level is very limited, please let me know if you have any mistakes! Don't forget if it helps!
give the thumbs-up 👍 Collect ✨ Attention ✌