Traversal of the first, middle, and last order of a binary tree -- Essence (each node is a "root" node)

The key point is to do some questions by yourself

Among the three methods of traversing binary trees
root - Left - Right
Left - root - Right
Left - Right - root
Remember that every node is a root
So when traversing the preamble , Will first “ Ignore ” Right subtree
When traversing the middle order , Will not print first The left subtree of the previous root （ Because maybe the left subtree of the previous root , It is also the root of other nodes ）
During subsequent traversal , Traverse each root , To print out the root node

Be careful ： Nodes traversed each time , In fact, they are all root nodes

1. The former sequence traversal （ Each traversal node is treated as the root ）

2. In the sequence traversal （ Only traverse the left subtree of the root , Then print the root ）

3. After the sequence traversal （ Only traverse the left and right subtrees , Then print the root ）

1. NLR： The former sequence traversal (Preorder Traversal Also called preorder traversal )—— Access root —> The left subtree of the root —> Right subtree of root .
2. LNR： In the sequence traversal (Inorder Traversal)—— The left subtree of the root —> The root node —> Right subtree of root .
3. LRN： After the sequence traversal (Postorder Traversal)—— The left subtree of the root —> Right subtree of root —> The root node

Preorder traversal results ：1 2 3 4 5 6（ Each traversal node is treated as the root ）
Middle order traversal result ：3 2 1 5 4 6（ Only traverse the left subtree of the root , Then print the root ）
Subsequent traversal results ：3 1 5 6 4 1（ Only traverse the left and right subtrees , Then print the root ）

    //  The former sequence traversal 
    void preOrder(TreeNode root) {
    
        if(root == null) return;
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    //  In the sequence traversal 
    void inOrder(TreeNode root) {
    
        if(root == null) return;
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    //  After the sequence traversal 
    void postOrder(TreeNode root) {
    
        if(root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }