1. 题目 的 description:

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

Problem 94

Example Description:

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

Example 2:

Input: root = [] Output: [] Input: root = [1] Output: [1]Copy the code

Tip:

The number of nodes in the tree is in the range [0, 100] -100 <= node. val <= 100Copy the code

Middle order traversal mode:

Two, recursive solution

Analysis of ideas:

The simplest solution to this problem is to use recursion. I write a function that passes in the root node of the binary tree that needs to be traversed. In the function, to determine whether root is a null node, it directly returns an empty array []. The operation is divided into three parts. The first part positions it to the bottom-left node (until it is empty), and the second part begins, at which point it presses root.val into array storage. In the operation of the three parts of the operation, until traversing to the bottom right leaf node.

AC code:

var inorderTraversal = function(root,array=[]) {
    if(root){
        inorderTraversal(root.left,array);/ / 1
        array.push(root.val);/ / 2
        inorderTraversal(root.right,array)/ / 3
    }
    return array;
}
Copy the code

Iterative problem solving

Analysis of ideas:

Using the stack of its operation, using the characteristics of the stack last in first out to get the due traversal results.

AC code:

var inorderTraversal = function(root){
    const stack=[];
    const result=[];
    while(root||stack.length>0) {while(root){// Double loop to find the leftmost leaf
            stack.push(root);
            root=root.left;
        }
        root=stack.pop();
        result.push(root.val);
        root=root.right;
    }
    return result;
}
Copy the code

Iv. Summary:

For the first time, I summarized the leetCode topic in the form of an article, which may not be in place, but with the output of more articles, it will be more and more perfect.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign