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

The title

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

Example 1:

Enter: root = [1,null,2,3]

Output: 31 [1]

Example 2:

Enter: root = []

Output: []

Example 3:

Enter: root = [1]

Output: [1]

Example 4:

Enter: root = [1,2]

Output: [2, 1]

Example 5:

Enter: root = [1,null,2]

Output: [1, 2]

 

Tip:

  • The number of nodes in the tree is in the range [0, 100]
  • -100 <= Node.val <= 100

 

Advanced:

Recursion is simple, can you do it iteratively?

Their thinking

Method one: recursion

First, we need to understand what middle order traversal of binary trees is: traversal of the tree in the same way that we visit the left subtree — the root node — the right subtree, and traversal of the left subtree or the right subtree in the same way until we have traversed the entire tree. Therefore, the whole traversal process naturally has the nature of recursion, we can directly use recursive function to simulate this process.

Define inorder(root) to represent the answer currently traversed to root, so by definition we simply recursively call inorder(root.left) to traverse the left subtree of root, and then add the value of root to the answer. Recursively call inorder(root.right) to traverse the right subtree of the root node. The recursion terminates when an empty node is encountered.

var inorderTraversal = function(root) {
    const res = [];
    const inorder = (root) = > {
        if(! root) {return;
        }
        inorder(root.left);
        res.push(root.val);
        inorder(root.right);
    }
    inorder(root);
    return res;
};
Copy the code

Complexity analysis

  • Time complexity: O(n)

    Where n is the number of nodes in the binary tree. Each node is accessed once and only once in a binary tree traversal.

  • Space complexity: O(n)

    The spatial complexity depends on the stack depth of the recursion, which is O(n) in the case of a binary tree as a chain

Method two: iteration

var inorderTraversal = function(root) {
    const res = [];
    const stk = [];
    while (root || stk.length) {
        while (root) {
            stk.push(root);
            root = root.left;
        }
        root = stk.pop();
        res.push(root.val);
        root = root.right;
    }
    return res;
};
Copy the code

Complexity analysis

  • Time complexity: O(n)

    Where n is the number of nodes in the binary tree. Each node is accessed once and only once in a binary tree traversal.

  • Space complexity: O(n)

    The spatial complexity depends on the stack depth, which is O(n) in the case of a binary tree as a chain.

conclusion

This is Xiaokui 🌻, as long as you turn your heart toward the sun, you will have warmth ~

Let’s overcome the algorithm together!!