My CSDN blog: blog.csdn.net/gdutxiaoxu my nuggets: juejin. Cn/user / 220747… Github: github.com/gdutxiaoxu/ wechat official account: Programmer Xu Gong

preface

When it comes to the four traversal modes of trees, you may think of the four traversal modes of trees at the first time, and quickly said its characteristics.

  1. Sequential (root-first) traversal: Visits the root node first, then the left and right children

  2. Middle-order traversal: Access the child first, then the root node and the right child

  3. Back-order traversal: access the left child first, then the right child, then the root node

  4. Layer traversal: Traversal from bottom to top based on the number of layers

And then when you have to write code by hand, can you do it?

  1. Recursion to achieve binary tree preorder, middle order, subsequent traversal

  2. Non – recursive binary tree implementation pre – order, middle order, subsequent traversal

  3. Achieve binary tree sequence traversal

Today, let’s look at how to do it.

Order traversal before, middle and after

Suppose you have the following tree

1 / \ 2 3 / \ 4 5 6Copy the code

Its first, middle and subsequent traversals are as follows

  • Hierarchical traversal order: [1, 2, 3, 4, 5, 6]

  • [1, 2, 4, 5, 3, 6]

  • Middle order traversal order: [4 2 5 1 3 6]

  • After order traversal order: [4 5 2 6 3 1]

Hierarchical traversal using BFS implementation, the use of BFS layer by layer traversal characteristics; DFS is used to realize pre-order, middle-order and post-order traversal.

Pre-order, mid-order and post-order traversal are the same except for the order in which nodes are accessed.

Recursive implementation of pre – order, order, order after traversal

1) before the order

void dfs(TreeNode root) {
    visit(root);
    dfs(root.left);
    dfs(root.right);
}
Copy the code

(2) in the sequence

void dfs(TreeNode root) {
    dfs(root.left);
    visit(root);
    dfs(root.right);
Copy the code

(3) after the order

void dfs(TreeNode root) {
    dfs(root.left);
    dfs(root.right);
    visit(root);
}
Copy the code

Non-recursive implementation of binary tree first order, middle order, order after traversal

Non – recursive implementation of binary tree prior traversal

144. Binary Tree Preorder Traversal (Medium)

Leetcode/Leetcode: leetcode-cn.com/problems/bi…

Class Solution {// iterate public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); while(root! =null || ! stack.empty()){ while(root! =null){ res.add(root.val); // Add the node to the result queue stack.push(root); // Keep pushing the left subtree of the node root = root.left; } root = stack.pop(); Root = root.right; // Go to the left subtree of the right subtree of the node (next loop)} return res; }}Copy the code

Non-recursive implementation of binary tree middle order traversal

94. Binary Tree Inorder Traversal (Medium)

Leetcode/Leetcode: leetcode-cn.com/problems/bi…

Class Solution {// iterate public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); while(root! =null || ! stack.empty()){ while(root! =null){ stack.push(root); // Keep pushing the left subtree of the node root = root.left; } root = stack.pop(); Res.add (root.val); // Add the node to the result queue root = root.right; // Go to the left subtree of the right subtree of the node (next loop)} return res; }}Copy the code

Non-recursive implementation of the binary tree after the order traversal

145. Binary Tree Postorder Traversal (Medium)

Leetcode/Leetcode: leetcode-cn.com/problems/bi…

The preceding traversal is root -> left -> right, and the latter is left -> right -> root. You can change the pre-order traversal to root -> right -> left so that the order is reversed from the post-order traversal.

// Change the end of the insertion queue to the beginning of the insertion queue. Class Solution {public List<Integer> postorderTraversal(TreeNode root) {LinkedList res = new LinkedList(); Stack<TreeNode> stack = new Stack<>(); TreeNode pre = null; while(root! =null || ! stack.empty()){ while(root! =null){ res.addFirst(root.val); // Insert stack.push(root); root = root.right; } root = stack.pop(); root = root.left; } return res; }}Copy the code

Non-recursive implementation of binary tree sequence traversal

Leetcode:leetcode.com/problems/bi…

class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); Queue<TreeNode> queue = new LinkedList<>(); if(root == null) return res; queue.add(root); while(! queue.isEmpty()){ int count = queue.size(); List<Integer> temp = new LinkedList<>(); for(int i=0; i<count; i++){ TreeNode node = queue.poll(); temp.add(node.val); if(node.left ! = null) queue.add(node.left); if(node.right ! = null) queue.add(node.right); } // Add to the first position res.add(0, temp); } return res; }}Copy the code

summary

  1. Recursive implementation of the binary tree front, middle and back traversal, this way is very simple, we must master

  2. Non-recursive way, in fact, it is not difficult, front, middle and back order traversal mode mainly by virtue of the characteristics of the stack, the way of order traversal mainly by virtue of the queue, we also want to master, more than two times, remember.

  3. Github address: github.com/gdutxiaoxu/…

Recommended reading

Android Startup Optimization (1) – Directed acyclic graph

Android startup optimization (2) – Topology sort principle and solution ideas

Android startup optimization (III) – AnchorTask open source now

Android Startup Optimization (4) – AnchorTask is implemented

Android Startup Optimization (5) – AnchorTask version 1.0.0 is now available

Android Startup Optimization (VI) – In-depth understanding of layout optimization