There are three main traversal modes for binary trees: pre-order traversal, mid-order traversal, and post-order traversal (and, of course, hierarchical traversal, which is beyond the scope of this article). For the root node, the former order is “first root, then left and finally right”, while the middle order is “first left, then root and finally right”, and the latter order is naturally “first left, then right and finally root”.

Realization of binary tree traversal, there are mainly recursion and iteration of the two methods, recursive method is relatively simple, here will not do the explanation, directly on the code

recursive

Class Solution {public List<Integer> res=new ArrayList<>(); public List<Integer> preorderTraversal(TreeNode root) { method(root); return res; } void method(TreeNode root){ if(root==null) return; res.add(root.val); method(root.left); method(root.right); } // Class Solution {List<Integer> List =new ArrayList(); public List<Integer> inorderTraversal(TreeNode root) { helper(root); return list; } void helper(TreeNode root){ if(root==null) return ; helper(root.left); list.add(root.val); helper(root.right); Class Solution {List<Integer>res=new ArrayList(); public List<Integer> postorderTraversal(TreeNode root) { helper(root); return res; } void helper(TreeNode root){ if(root==null) return; helper(root.left); helper(root.right); res.add(root.val); }}Copy the code

The iteration

Iteration is a little more difficult than recursion, but it is actually easier to understand, with the help of the stack “first in, last out, last in, first out” feature

Before the order

The preorder traversal is “root -> left -> right”. We start from the root node and continue traversal to its left child node, adding the traversal value to the result set. At the same time, a stack is used to push the traversed node onto the stack, so that when the traversed left node is null, a node in the stack can be ejected and traversed from the right node of the node

public List<Integer> preorderTraversal(TreeNode root) { List<Integer>res=new ArrayList(); Deque<TreeNode>stack=new LinkedList(); TreeNode node=root; while(node! =null||! stack.isEmpty()){ if(node! =null){ res.add(node.val); stack.push(node); node=node.left; }else{ node=stack.pop(); node=node.right; } } return res; }Copy the code

In the sequence

The main difference is that the order of middle-order traversal is “left -> root -> right”, so the value of the node cannot be added to the result set when the node is traversed. Instead, the value of the node can be added to the result set when the node is popped from the stack

public List<Integer> inorderTraversal(TreeNode root) { List<Integer>res=new ArrayList(); Deque<TreeNode>stack=new LinkedList(); TreeNode node=root; while(node! =null||! stack.isEmpty()){ if(node! =null){ stack.push(node); node=node.left; }else{ node=stack.pop(); res.add(node.val); node=node.right; } } return res; }Copy the code

After the order

After sequence traversal of thinking with the above two slightly different, because the traversal sequence after sequence is “left – > right – > root”, according to the previous two kind of method is unable to realize the traversal sequence, then we can change ideas, to “left – > right – > root” into “root – > right – > left”, after will traverse to the value of the head insert method is used to insert the result set. The other implementations are consistent with the previous order traversal

public List<Integer> postorderTraversal(TreeNode root) { List<Integer>res=new ArrayList(); TreeNode node=root; Deque<TreeNode>stack=new LinkedList(); while(node! =null||! stack.isEmpty()){ if(node! =null){ res.add(0,node.val); stack.push(node); node=node.right; }else{ node=stack.pop(); node=node.left; } } return res; }Copy the code