Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

This article also participated in the “Digitalstar Project” to win a creative gift package and creative incentive money

Code shrimp is a sand carving and funny boy who likes listening to music, playing games and writing as well as most of his friends. The days are still very long, let’s refuel our efforts together 🌈

If you feel well written, ball ball a concern oh 😉


preface

Binary tree traversal corresponding address:

Force button: binary tree traversal address

Force button: sequential traversal address in a binary tree

Force button: the address traversed backwards in the binary tree

Force button: binary tree traversal address


Binary tree sequence traversal

Use breadth First Search (BFS)

public class Main {



    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> res = new ArrayList<>();
        if(root == null)
            return res;

        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while(! queue.isEmpty()) {int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while (size-- > 0) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left ! =null) {
                    queue.add(node.left);
                }
                if(node.right ! =null) {
                    queue.add(node.right);
                }
            }
            res.add(list);
        }

        returnres; }}class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right; }}Copy the code


The recursive method


Binary tree forward traversal


public class Main {


    List<Integer> res;
    public List<Integer> preorderTraversal(TreeNode root) {
        res = new ArrayList<>();
        if(root == null)
            return res;
        preTreeNode(root);
        return res;
    }

    private void preTreeNode(TreeNode root) {
        if(root == null) return; res.add(root.val); preTreeNode(root.left); preTreeNode(root.right); }}class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right; }}Copy the code

Complexity analysis

  • Time complexity: O(n), where n is the number of nodes in the binary tree. Each node is traversed exactly once.

  • Space complexity: O(n), is the stack overhead during recursion, O(logn) in the average case, O(n) in the worst case, tree chain-like, O(n).


Sequential traversal in a binary tree

public class Main {


    List<Integer> res;

    public List<Integer> inorderTraversal(TreeNode root) {
        res = new ArrayList<>();
        if (root == null)
            return res;

        midTreeNode(root);
        return res;
    }

    private void midTreeNode(TreeNode root) {
        if (root == null) return; midTreeNode(root.left); res.add(root.val); midTreeNode(root.right); }}class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right; }}Copy the code


Backorder traversal of binary tree

public class Main {
    

    List<Integer> res;
    public List<Integer> postorderTraversal(TreeNode root) {
        res = new ArrayList<>();
        if(root == null)
            return res;

        postTreeNode(root);
        return res;
    }

    private void postTreeNode(TreeNode root) {
        if(root == null) return; postTreeNode(root.left); postTreeNode(root.right); res.add(root.val); }}class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right; }}Copy the code


Iterative method


Binary tree forward traversal

It is similar to the recursive method, but the hidden stack in the recursion is shown

Because of the nature of the stack, we need to push the right child onto the stack first and then push the left child, so that when we take it out, we take the left child out first.


public class Main {

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

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right; }}Copy the code


Sequential traversal in a binary tree

The middle-order traversal outputs nodes in left-right order. So we push the left subtree of the node into the stack as much as possible, so that the top element of the stack is the leftmost node. After the pop, we push the right child of the node into the stack, so that the element is traversed in the middle order


public class Main {


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

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right; }}Copy the code


Backorder traversal of binary tree

  • The root node is first pushed
  • The root node is first out of the stack, followed by the right child, and then the left child
  • Push the left child node
  • Push the right child node onto the stack
  • Since the unstack order is “root right left,” you need to insert elements at the beginning of the list each time
public class Main {


    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if (root == null)
            return result;
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);   
        while(! stack.isEmpty()) { TreeNode node = stack.pop();if(node.left ! =null)
                stack.push(node.left);  
            if(node.right ! =null) {
                stack.push(node.right); 
            }
            result.add(0, node.val); 
        }
        returnresult; }}class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right; }}Copy the code

💖 finally

I am aCode pipi shrimp, a prawns lover who loves to share knowledge, will update useful blog posts in the future, looking forward to your attention!!

Creation is not easy, if this blog is helpful to you, I hope you can key three even oh! Thank you for your support. See you next time