Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.
There are two types of traversal for binary trees, one is depth-first traversal, which we call DFS, and the other is breadth-first traversal, which we call BFS; Depth-first traversal is implemented in two ways, one is recursion and the other is iteration, while breadth-first traversal is implemented by queue, which is called sequential traversal.
Depth-first traversal
First of all, starting from recursion, summarize three methods of binary tree depth-first traversal, namely pre-order traversal, middle-order traversal and post-order traversal.
The TreeNode is a binary TreeNode class. The TreeNode is a binary TreeNode class. The TreeNode is a binary TreeNode class.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(){}
TreeNode(int val){
this.val = val
}
TreeNode(int val, TreeNode left, TreeNode right){
this.val = val;
this.left = left;
this.right = right; }}Copy the codeThe recursive method
The former sequence traversal
The properties of binary tree traversal are: root node, left node, right node.
class Solution {
public List<Integer> res;
public List<Integer> preOrderTraveral(TreeNode root){
if (root == null) return new ArrayList();
res = new ArrayList();
/ / before order
preOrder(root);
return res;
}
public void preOrder(TreeNode root){
if (root == null) return;
res.add(root.val); / /
preOrder(root.left); / / left
preOrder(root.right); / / right}}Copy the codeIn the sequence traversal
The properties of sequential traversal in binary trees are: left node, root node, right node.
class Solution {
public List<Integer> res;
public List<Integer> inOrderTraveral(TreeNode root){
if (root == null) return new ArrayList();
res = new ArrayList();
/ / in the sequence
inOrder(root);
return res;
}
public void inOrder(TreeNode root){
if (root == null) return;
preOrder(root.left); / / left
res.add(root.val); / /
preOrder(root.right); / / right}}Copy the codeAfter the sequence traversal
The properties of backward traversal in binary trees are: left node, right node, root node.
class Solution {
public List<Integer> res;
public List<Integer> postOrderTraveral(TreeNode root){
if (root == null) return new ArrayList();
res = new ArrayList();
/ / after order
postOrder(root);
return res;
}
public void postOrder(TreeNode root){
if (root == null) return;
preOrder(root.left); / / left
preOrder(root.right); / / right
res.add(root.val); / /}}Copy the codeIterative method
In binary trees, if iteration is used to traverse, the stack must be used to do so.
The former sequence traversal
Since the nature of the stack is first and then out, we need to push the right child first, then push the left child, so that the order of the stack will be: middle – left – right.
Using stack to achieve binary tree prior traversal code is as follows:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) return new ArrayList<Integer>();
List<Integer> list = new ArrayList();
Stack<TreeNode> stack = new Stack();
stack.push(root);
while(! stack.isEmpty()){ TreeNode node = stack.pop(); list.add(node.val);// Key code
if(node.right ! =null) stack.push(node.right);
if(node.left ! =null) stack.push(node.left);
}
returnlist; }}Copy the codeIn the sequence traversal
Middle-order traversal is left-middle-right, so we need to find the left child at the bottom of the binary tree first, so we need to find a layer by layer, until we reach the bottom left of the tree, in this step, we can borrow Pointers to help access nodes, use the stack to store the elements on the node.
The middle order traversal code of binary tree using stack is as follows:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
if(root == null) return new ArrayList();
List<Integer> list = new ArrayList();
Stack<TreeNode> stack = new Stack();
TreeNode curr = root;
while(curr ! =null| |! stack.isEmpty()){// Key code
if(curr ! =null){
stack.push(curr);
curr = curr.left;
}else{ TreeNode node = stack.pop(); list.add(node.val); curr = node.right; }}returnlist; }}Copy the codeAfter the sequence traversal
Since we have already written the preorder traversal above, we just need to make some changes in its code to implement the postorder traversal.
Since the order of post-order traversal is left-right-middle, and the order of pre-order traversal is middle-left-right, we can first switch the order of left-child and right-child to the stack, and then flip the List array to implement post-order traversal based on the code of pre-order traversal.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) return new ArrayList<Integer>();
List<Integer> list = new ArrayList();
Stack<TreeNode> stack = new Stack();
stack.push(root);
while(! stack.isEmpty()){ TreeNode node = stack.pop(); list.add(node.val);// Key code
if(node.left ! =null) stack.push(node.left);
if(node.right ! =null) stack.push(node.right);
}
returnCollections.reverse(list); }}Copy the codeBreadth-first traversal
The way a sequence traverses a binary tree is to traverse the tree layer by layer from left to right. In this case, we need to use the queue, the first-in, first-out feature of the queue to traverse the binary tree layer by layer.
Sequence traversal
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if (root == null) {
return ret;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(! queue.isEmpty()) { List<Integer> level =new ArrayList<Integer>();
int currentLevelSize = queue.size();
for (int i = 1; i <= currentLevelSize; ++i) {
TreeNode node = queue.poll();
level.add(node.val);
if(node.left ! =null) {
queue.offer(node.left);
}
if(node.right ! =null) {
queue.offer(node.right);
}
}
ret.add(level);
}
returnret; }}Copy the codeLearn binary tree sequence traversal, can be completed in one breath the following ten questions:
- 102. Sequence traversal of binary trees
- 107. Hierarchical traversal of binary trees II
- 199. Right view of binary trees
- 637. Mean level of binary trees
- 429. Antecedent traversal of N fork trees
- Look for the maximum value in each tree line
- 116. Populate the next right node pointer for each node
- 117. Populate the next right node pointer II for each node
- 104. Maximum depth of a binary tree
- 111. Minimum depth of a binary tree
The last
Ok, the summary of binary tree traversal is over here. To review, the traversal of binary tree is divided into depth-first traversal and breadth-first traversal, among which depth-first traversal can be realized by recursion and iteration. Breadth-first traversal can be realized by sequential traversal. We also used stack and queue data structures. I believe that after reading this article, you will have a certain understanding of binary tree traversal, thank you for reading.
Previous articles:
- StoreKit2 smells this good? Yeah, I tried it. It smells good
- After reading this article, I am no longer afraid of being asked how to construct a binary tree.
- The game guys are trying to get people to pay again. That’s bad!
- Take you rolled a netease holding cloud music home | adapter
- Netease Cloud Music Home Page (3)
- Netease Cloud Music Home Page (2)
- Netease Cloud Music Home Page (a)
- Does the code need comments? Write and you lose
- I would not study in Codable for a long time. They are for fun
- IOS handles web data gracefully. Do you really? Why don’t you read this one
- UICollectionView custom layout! This one is enough
Please drink a cup ☕️ + attention oh ~
- After reading, remember to give me a thumbs-up oh, there is 👍 power
- Follow the public number – HelloWorld Jie Shao, the first time push new posture
Finally, creation is not easy, if it is helpful to you, I hope you can praise and support, what questions can also be discussed in the comments section 😄 ~