“This is the 15th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

preface

The middle order traversal of the binary tree of question 94 is shown as follows:

Given the root node of a binary tree, return its middle-order traversal.

Example 1:

Input: root = [1,null,2,3]Copy the code

A, thinking

This problem does not need too much introduction, the binary tree before the middle order is a very classic problem.

This is a good time to review the basics of binary trees, do you remember when to traverse a binary tree in order?

  • Foreorder traversal: first root node, then find the left child, and finally find the right child
  • Middle order traversal: first find the left child, then find the root node, and finally find the right child
  • Back-order traversal: first find the left child, then find the right child, and finally find the root node

Example as an example, the results of its sequential traversal before, during and after are shown as follows:

  1. The former sequence traversal

  1. In the sequence traversal

  1. After the sequence traversal

There is a key point to remember about the order before, after and after: before, after and after refers to the position of the root node. (For example, in order traversal, the root node is in the middle, that is, after the front root.) Another point to note is that the order of traversal means that each node is traversed in the same order. (Take middle-order traversal as an example, as long as the left child of the subtree is not empty, it will be read first)

Second, the implementation

The implementation code

The code can be implemented in two ways: recursion and traversal (recursion is recommended because the code is more concise and the time and space complexity of both are the same).

recursive

List<Integer> ret= new ArrayList<>();
/** * order traversal (left root right) */
public List<Integer> inorderTraversal(TreeNode root) {
    infixOrder(root);
    return ret;
}

/ / in the sequence
public void infixOrder(TreeNode root) {
    if (root == null)
        return;
    // Start with the left child
    infixOrder(root.left);
    ret.add(root.val);
    // Back to find the right child
    infixOrder(root.right);
}
Copy the code

traverse

    public List<Integer> inorderTraversal1(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        while(root ! =null| |! stack.isEmpty()) {// push all left nodes onto the stack first
            while(root ! =null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
Copy the code

The test code

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1.null.new TreeNode(2.new TreeNode(3), null));
        new Number94().inorderTraversal(treeNode);
    }
Copy the code

The results of

My submission results here use recursion, and the beat rate with traversal is about the same.

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section