Today is LeetCode topic 60 article, we will look at LeetCode 94, binary tree middle order traversal.

The official difficulty of this question is Medium, with 3,304 upvotes and 140 downvotes, with a pass rate of 63.2%, which is quite high among Medium questions. This problem is very basic, can be said to be a programmer must know one of the algorithm problems.

Let’s look at the question first.

The question

Given a binary tree, return the result of its sequential traversal.

The sample

Input: [1, null, 2, 3]

   1

    \

     2

    /

   3



Output: 31 [1]

Copy the code

It’s very easy to do this problem recursively. Can you do it without recursion?

Answer key

Let’s first introduce the middle-order traversal of binary trees. There are three ways of traversal of binary trees, namely, pre-order, middle-order and post-order. For starters, these three orders may seem silly and indistinguishable. It’s very simple to say, traversal means the order in which we recursively iterate.

Let’s say the node we recurse to so far is U, and it has left and right children. We have three strategies to ensure that the left child always visits before the right child. The first way is to add U to the access sequence, and then traverse the left and right subtrees separately. The second way is to recursively traverse the left subtree, then add U to the access sequence, and finally traverse the right subtree. The third strategy is to recursively traverse the left and right subtrees and finally add U to the access sequence.

What’s the difference between these three strategies? In fact, the biggest difference lies in the order in which u is added to the access sequence. If u is added first and then accessed, then it is ordered first. If the left subtree is accessed first and u is added, it is middle order, and if the left subtree is recursed first and u is added last, it is post-order. To put it bluntly, the first addition of u is pre-order, the middle addition is middle order, and the last addition is post-order. If you’re still a little confused, let’s take a look at the code and make it very clear.

# order first

def dfs(u):

    visited.append(u)

    dfs(u.left)

    dfs(u.right)

    

    

# in the order

def dfs(u):

    dfs(u.left)

    visited.append(u)

    dfs(u.right)

    

    

# after the order

def dfs(u):

    dfs(u.left)

    dfs(u.right)

    visited.append(u)

Copy the code

But they’re asking us not to do it recursively, so how do we do that?

There’s a way to do it, and we need to start with the implementation of recursion. We know that inside the compiler, when we call another function from one function, the function information is stored in a stack structure. Each node in the middle of the stack records the name of the function and where it is currently running, some intermediate variables, and so on. So when we recurse, we’re actually pushing the current function over and over again.


For example, if our DFS function recursively calls the DFS function at line 5, the compiler’s internal stack will record [(DFS, 5), (DFS, 1)]. If we call sum on the first line of DFS, the compiler will add sum to the stack: [(DFS, 5), (DFS, 1), (sum, 1)]. When the function completes, it is popped from the stack.

In short, recursion is simply the use of the compiler’s own stack structure to simplify the writing of our code and functionality. Since we are not allowed to use recursion in this problem, we will have to simulate the process using the stack ourselves. The process is a little more complicated because we need to maintain the elements in the stack ourselves.

In this problem, we use a stack to record the nodes in the tree. The node at the top of the stack is the node currently accessed.

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

class Solution:

    def inorderTraversal(self, root: TreeNode) -> List[int]:

        ret = []

        stack = []

        stack.append(root)

        while len(stack) > 0:

            Get the top point of the stack

            cur = stack[- 1]

            if cur is None:

                stack.pop()

                continue

                

            If the left child exists, traverse the left child first

            if cur.left is not None:

                stack.append(cur.left)

                Set the left pointer to null to prevent an infinite loop

                You can also use set to maintain it

                cur.left = None

                continue

                

            Add the sequence at the end of the left iteration

            ret.append(cur.val)

            stack.pop()

            if cur.right is not None:

                stack.append(cur.right)

                

        return ret

Copy the code

conclusion

If it’s just traversal of a binary tree, anyone can do this, but if you can’t use recursion, it’s hard power. It requires a deep understanding of the underlying principles of recursion and familiarity with the data structure stack. The logic of this code is not difficult to understand, but the implementation is quite exercise people, I recommend you try.

This is the end of today’s article, if you like this article, please invite a wave of quality sanlian, give me a little support (follow, forward, like).

Original link, ask a concern

– END –