Binary tree traversal series 01- Recursive traversal and recursive order

One 、 introduction

1. The first sequence traversal

   Preorder traversal is also called root first traversal , seeing the name of a thing one thinks of its function , In this traversal method , First, traverse the root node , Then traverse the left child of the root node first , Then traverse the right child of the root node in order , From this traversal rule , We can see that , There is an obvious recursive meaning , Therefore, it is a common method to use recursive method to realize the pre order traversal of the tree , It's simple

2. In the sequence traversal

   In the sequence traversal , Unlike preorder traversal , The middle order traversal does not access the root node first , The middle order traversal first accesses the left child of the root node , Then access the root node , Finally, access the right child of the root node , The meaning of this is obvious , Is to put the traversal of the root node in the middle of the left child and the right child

3. After the sequence traversal

   With the introduction of preorder traversal and middle order traversal , The post order traversal is very straightforward , First visit the left child of the root node , Then access the right child of the root node , Finally, visit Gen , Although post order traversal sounds as simple as pre order and middle order , In fact, the recursive implementation of subsequent traversal is also very simple , But the non recursive implementation of post order traversal is the most complex

Two 、 Three traversal recursive implementations

2.1 The first sequence traversal

public void preOrder(TreeNode root) {
    
    if (root == null) {
    
        return;
    }
    Systen.out.println(root.val);
    preOrder(root.left);
    preOrder(root.right);
}

2.2 In the sequence traversal

public void inOrder(TreeNode root) {
    
    if (root == null) {
    
        return;
    }
    preOrder(root.left);
    Systen.out.println(root.val);
    preOrder(root.right);
}

2.3 After the sequence traversal

public void postOrder(TreeNode root) {
    
    if (root == null) {
    
        return;
    }
    preOrder(root.left);
    preOrder(root.right);
    Systen.out.println(root.val);
}

3、 ... and 、 Discussion on the generality of recursive writing

The above three recursive traversals can be written as follows

public void visit(TreeNode root) {
    
    if (root == null) {
    
        return;
    }
    //  If you deal with it here , So that's the order 
    visit(root.left);
    //  If you deal with it here , So it's the middle order 
    visit(root.right);
    //  If you deal with it here , So that's the sequence 
}

3.1 Recursive graph and recursive order

We can draw the above visit Recursive graph of , As shown in the figure below , The red circle indicates the order of access , among null Nodes also need to be accessed once , According to the above recursive access order , You can get the access order of each element ：1、2、4、7、7、7、4、4、2、5、5、5、2、1、3、3、6、6、6、3、1, This is the recursive order , By observing the recursive order , We can find out , Each element appears three times , Why? , In fact, we can easily draw this conclusion by observing the code ：

public void visit(TreeNode root) {
     
    if (root == null) {
     
        return;
    }
   	// root First visit 
    visit(root.left);
    //  After the previous layer of recursion ends , Back to the current recursive stack ,root Second visit 
    visit(root.right);
    // root Visited for the third time 
}

in other words , Traversal of first order, middle order and second order , It's essentially the same thing , The difference is that , In the current recursive order , When an element appears for several times, it is processed , Preorder is to deal with... The first time an element appears , Middle order is to process the element the second time it appears , Post order is to process the element when it last appears