Traversal binary tree

Catalog

Four ways to traverse a binary tree

1. The first sequence traversal

① recursive

② Non recursive

2. In the sequence traversal

① recursive

② Non recursive

3. After the sequence traversal

① recursive

② Non recursive

4. Sequence traversal

Four ways to traverse a binary tree

1. The first sequence traversal

① recursive

public static void preOrder(Node root) {
        if (root==null){
            return;
        }
        // Access the root node first 
        System.out.print(root.val);
        // Recursively traverses the left subtree 
        preOrder(root.left);
        // Recursively traverses the right subtree 
        preOrder(root.right);
    }

② Non recursive

( Similar sequence traversal ）
    1. Create a stack 
    2. Stack the root node 
    3. Take out the top element of the stack and access this node 
    4. Stack the right subtree of the current node , Left subtree into stack 
    5. go back to 3 repeat 

public static void preOrder(TreeNode root){
        if (root==null){
            return;
        }
        // First create a stack 
        Stack<TreeNode> stack=new Stack<>();
        // Root node stack 
        stack.push(root);
        while(!stack.empty()){
            TreeNode cur=stack.pop();
            System.out.print(cur.val);
            if (cur.right!=null){
                stack.push(cur.right);
            }
            if (cur.left!=null){
                stack.push(cur.left);
            }
        }
    }

2. In the sequence traversal

① recursive

 public static void inOrder(Node root) {
        if (root==null){
            return;
        }
        // First recursively traverse the left subtree 
        inOrder(root.left);
        // Access the root node again 
        System.out.print(root.val);
        // Recursively traverses the right subtree 
        inOrder(root.right);
    }

② Non recursive

1. Create a stack 
2. Create a reference cur, from root set out , Run all the way to the left , All non empty nodes encountered are stacked , When cur encounter null When , End of cycle 
3. Take out the top element of the stack , And access 
( The characteristic of Zhongxu is to go all the way to the left , The left subtree of a node is empty , To access the root node )
4. Give Way cur Point to the right subtree of the node , go back to 2 Carry on 

    public static void inOrder(TreeNode root){
        if (root==null){
            return;
        }
        // First create a stack 
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(true){
            // The inner circle is responsible for cur Go left and merge into the stack 
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            // When the above cycle ends ,cur It's already null
            // Take out the top element of the stack , And visit 
            if (stack.isEmpty()){
                break;
            }
            TreeNode top=stack.pop();
            System.out.print(top.val);

            // Give Way cur from top Start from the right subtree of and repeat the above process 
            cur=top.right;
        }
    }

3. After the sequence traversal

① recursive

public static void postOrder(Node root) {
        if (root==null){
            return;
        }
        // First recursively traverse the left subtree 
        postOrder(root.left);
        // Then recursively traverse the right subtree 
        postOrder(root.right);
        // Finally, the root node is accessed 
        System.out.print(root.val);
    }

② Non recursive

1. Create a stack 
2. Create a reference cur, from root set out , Run all the way to the left , Non empty nodes encountered will be put on the stack , When cur encounter null Stop when it's time 
3. Top stack elements cannot be accessed immediately , We have to decide first ：
    a) If the right subtree at the top of the stack is empty , Then you can access this element , Access and stack at the same time 
    b) If the right subtree of the top element of the stack has been visited before , You can also access this element 
  The current element cannot be accessed , let cur Point to the right subtree at the top of the stack , repeat 2

public static void postOrder(TreeNode root){
        if (root==null){
            return;
        }
        //1. Create a stack 
        Stack<TreeNode> stack=new Stack<>();
        //2. Create a reference cur, from root set out 
        TreeNode cur=root;
        // Use prev Represents the previous element of the traversal result 
        TreeNode prev=null;
        while(true){
        //3. Give Way cur Go to the left , If you encounter a non empty node, it will be put on the stack 
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            //4. Take out the top element of the stack and judge whether it can be accessed 
            if (stack.isEmpty()){
                break;
            }
            // You can't directly pop, Whether this node can be accessed is unknown 
            // It must be accessed to get out of the stack 
            TreeNode top=stack.peek();
            if (top.right==null || top.right==prev){
                // Can access this node 
                System.out.print(top.val);
                stack.pop();
                prev=top;
            }else{
                cur=top.right;
            }
        }
    }

4. Sequence traversal

1. First put the root node in the queue

2. Out of the queue , And access this node

3. Put the left and right subtrees of the current node into the queue again （null No matter ）

4. Go back to step 2 and continue to cycle

public static void levelOrder(Node root){
        if (root==null){
            return;
        }
        // Create a queue 
        Queue<Node> queue=new LinkedList<>();
        // Put the root node in the queue 
        queue.offer(root);
        // Loop to get the first element in the queue 
        while(true){
            Node cur=queue.poll();
            if (cur==null){
                break;
            }
            // Access current node 
            System.out.println(cur.val);
            // The left and right subtrees are queued 
            if (cur.left!=null) {
                queue.offer(cur.left);
            }
            if (cur.right!=null) {
                queue.offer(cur.right);
            }
        }
    }