1. The subject

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: The recursive algorithm is simple, can you do it with an iterative algorithm?

2. The answer

2.1 Idea 1 (Recursion)

Recursively, finitely traverses the left subtree

The code is as follows:

/** * Definition for a binary tree node. * public 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; *} *} */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        inorderTraversal(root, list);
        return list;
    }

    public void inorderTraversal(TreeNode root, List<Integer> list) {
        if (root == null) {
           return;
        }

        if(root.left ! =null) {
            inorderTraversal(root.left, list);
        }
        list.add(root.val);
        if(root.right ! =null) { inorderTraversal(root.right, list); }}}Copy the code

Time complexity

O(n)

Spatial complexity

O(n), because of recursion, caches the call stack, which is at its worst when the binary tree is weakened to a class list structure

Submit the results

As mentioned earlier, be aware of stack overflows and double computations when using recursion. In this case, you might encounter a situation where the binary tree depth is too high, causing the recursive call stack depth to be too high, even though the time complexity is good.

2.2 Idea 2 (Non-recursive)

Use iterative algorithms to solve the problem.

In fact, it feels more direct to use the backtracking algorithm. The left subtree is traversed from the root node until the left subtree is null. In this case, we need to go back to the parent node of the current node, put the value of the node into the result, and traverse the left subtree with the right subtree as the root node until all values are traversed.

The real concern is how to go back to the parent of the last node. You need a data structure to store the location of the current execution.

The code is as follows:

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        List<TreeNode> cache = new ArrayList<>();

        while(root ! =null| |! cache.isEmpty()) {if(root ! =null) {
                cache.add(root);
                root = root.left;
            } else {
                root = cache.remove(cache.size() - 1); list.add(root.val); root = root.right; }}returnlist; }}Copy the code

Time complexity

O(n)

Spatial complexity

O(n)

Submit the results