For the three traversal methods of binary tree, whether simple recursive writing method, or iterative writing method, are easy to be tested in the interview, so this article will explain this common knowledge points to explain clearly.
1. Antecedent traversal of binary trees (LeetCode 144)
The key to pre-order traversal is to traverse the root node, then the left subtree, and then the right subtree.
Namely: root → left → right
(1) Recursive writing
The recursion is obvious because the code is simple and easy to understand, as follows:
class Solution {
List<Integer> res = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null) return res;
dfs(root);
return res;
}
public void dfs(TreeNode root){
if(root == null) return ;
res.add(root.val); // Iterate over the root node first
dfs(root.left); // Walk through the left subtree again
dfs(root.right); // Walk through the right subtree again}}Copy the code(2) Iterative writing
To change from recursion to iteration, we need to use a very important data structure, the stack, to hold our last node, to keep track of where we came from, so that when we’re done with a node, we can go back through the stack, and that’s the core of iterative writing.
The code is as follows:
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stk = new Stack<>();
if(root == null) return res;
while(root ! =null| |! stk.isEmpty()){while(root ! =null){
res.add(root.val); // Iterate over the root node
stk.push(root); // Add the root node to the stack so that we can go back to the previous step
root = root.left; // Iterate over the left subtree
}
root = stk.pop(); // Exit the loop with root null, go back to the previous step (i.e. top element)
root = root.right; // Iterate over its right subtree
}
returnres; }}Copy the code2. Middle order traversal of binary trees (LeetCode 94)
The key to middle-order traversal is to traverse the left subtree first, then the root node, and finally the right subtree.
Namely: left → root → right.
(1) Recursive writing
class Solution {
List<Integer> res = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
if(root == null) return res;
dfs(root);
return res;
}
public void dfs(TreeNode root){
if(root == null) return ;
dfs(root.left); // Iterate over the left subtree
res.add(root.val); // Iterate over the root node
dfs(root.right); // Iterate over the right subtree}}Copy the code(2) Iterative writing
In the same way, using a stack to record our traversal path, the code is very similar to the preceding traversal.
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stk = new Stack<>();
if(root == null) return res;
while(root ! =null| |! stk.isEmpty()){while(root ! =null){
stk.push(root); // Record the traversal path
root = root.left; // Iterate over the left subtree
}
root = stk.pop(); // Exit the loop with root null and go back to the top of the stack
res.add(root.val); // Iterate over the root node
root = root.right; // Iterate over the right subtree
}
returnres; }}Copy the codeCompared with the previous iteration, it can be found that the position of res.add(root.val) has changed, so it is easier to remember.
3. Post-order traversal of binary trees (LeetCode 145)
The key to back-order traversal is to traverse the left subtree first, then the right subtree, and finally the root node.
Namely: left → right → root.
(1) Recursive writing
class Solution {
List<Integer> res = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
if(root == null) return res;
dfs(root);
return res;
}
public void dfs(TreeNode root){
if(root == null) return ;
dfs(root.left); // Iterate over the left subtree
dfs(root.right); // Iterate over the right subtree
res.add(root.val); // Iterate over the root node}}Copy the code(2) Iterative writing
If we write directly, we will find that it is not easy to write. So we can observe the characteristics. The order of pre-order traversal is: root left and right, the order of post-order traversal is: left and right root, if the result of pre-order traversal is reversed: The difference between the order of right and left roots and the order of post-traversal is in the order of left and right subtrees, so the iterative writing method of post-traversal can be slightly modified in the iterative writing method of pre-traversal.
That is, the root node is traversed, the right subtree is traversed, and the left subtree is traversed. The result is finally reversed, a backward traversal of the binary tree.
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stk = new Stack<>();
if(root == null) return res;
while(root ! =null| |! stk.isEmpty()){while(root ! =null){
res.add(root.val); // Iterate over the root node
stk.push(root); // Record the traversal path
root = root.right; // Iterate over the right subtree
}
root = stk.pop(); // Exit the loop with root null and go back to the top of the stack
root = root.left; // Iterate over the left subtree
}
Collections.reverse(res); // Reverse the result
returnres; }}Copy the codeconclusion
We can find that, in fact, the iterative writing of the first, middle and last order traversal of the binary tree is very similar, which is easy to remember directly after we only need to understand.
The difference between pre-order traversal and mid-order traversal code is that the position of a line of code changes;
Postorder traversal is modified slightly on the basis of preorder traversal;
So just three things to keep in mind:
(1) The iterative writing method needs to use the stack
(2) The loop is while(root! = null || ! stk.isEmpty())
(3) front order traversal idea, order traversal change a line of code position, after order traversal: root right left finally reverse the answer
Binary tree traversal is that simple ~