preface

So before we do that, let’s just kind of get a sense of how binary trees can be traversed.

Why are they called preorder, postorder, middle order?

A binary tree consists of the root, left and right subtrees. If D, L, and R represent traversal of the root, left, and right subtrees respectively, there are six traversal modes of the binary tree: DLR, DRL, LDR, LRD, RDL, and RLD. Since there is no essential difference in algorithm design between traversing the left subtree first and traversing the right subtree first, only three methods are discussed:

DLR– Forward traversal (root first, left to right, root of a tree always in front of left subtree, left subtree always in front of right subtree)

LDR- Middle order traversal (root in middle, left to right, left subtree of a tree always in front of root, root always in front of right subtree)

LRD– Backward traversal (root behind, left to right, left subtree of a tree always in front of right subtree, right subtree always in front of root)

The former sequence traversal

A front-order traversal first visits the root, then the left subtree, and finally the right subtree. When traversing the left and right subtrees, we still visit the root first, then the left subtree, and finally the right subtree.

If the binary tree is empty, end the return, otherwise:

  • (1) Access the root node.
  • (2) The left subtree is traversed in front order.
  • (3) The right subtree is traversed in front order.

Note that the forward traversal method is still used when traversing the left and right subtrees. The binary tree is shown

Foreorder traversal result: ABDECF can determine the foreorder traversal if it knows the post-order traversal and middle-order traversal.

The former sequence traversal

In the sequence traversal

A middle-order traversal first traverses the left subtree, then the root, and finally the right subtree. If the binary tree is empty, end the return, otherwise:

  • (1) In order to traverse the left subtree

  • (2) Access the root node

  • (3) In order to traverse the right subtree

As shown in the figure, binary tree, middle-order traversal result: DBEAFC

In the sequence traversal

After the sequence traversal

Back-order traversal first traverses the left subtree, then the right subtree, and finally the root. When traversing the left and right subtrees, the left subtree is traversed first, then the right subtree, and finally the root. That is:

If the binary tree is empty, end the return, otherwise:

  • (1) The left subtree is traversed sequentially
  • (2) The right subtree is traversed sequentially
  • (3) Access the root node

As shown in the figure, post-ordered traversal results: DEBFCA can determine post-ordered traversal if it knows pre-ordered traversal and middle-ordered traversal

After the sequence traversal

Subject to introduce

94. Middle order traversal of binary trees

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

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

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

Example 5:

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

Tip:

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

Their thinking

It is required to return the middle order traversal of a given binary tree root. According to the description of the middle order traversal in the preface, we will solve this problem in this order.

We use the recursive function inOrder to simulate the binary tree traversal process.

According to the above definition, the steps to solve the problem are as follows:

  • Recursive callsinOrder(root.left)To traverserootThe left subtree of a node
  • thenrootThe value of the nodevalJoin the answer
  • Call recursivelyinOrder(root.right)To traverserootThe right subtree of the node.

The problem solving code

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

Swipe questions and punch out records

Here is the previous swipe card records, you can have a look, if you have any different views and views or feel what is wrong, welcome to leave a message in the comment area! 🙏 🙏 🙏

[LeetCode0303 topic area and retrieval – array immutable] | punch brush

[LeetCode1200. Minimum absolute difference] | punch brush

[LeetCode0304 topic 2 d area and retrieval – matrix immutable] | punch brush

[LeetCode11 topic containers of most water] | punch brush

[LeetCode0338 topic bit count] | punch brush

[LeetCode209 topic length minimum subarray] | punch brush

[LeetCode236 topic in recent common ancestor of binary tree] | punch brush

[LeetCode141 topic circular linked list] | punch brush

[LeetCode53 topic most architectural sequence and] | punch brush

[LeetCode48 topic rotating images] | punch brush

[LeetCode155 topic minimum stack] | punch brush

[LeetCode1124 problem well, the longest period of a] | punch brush

[LeetCode274 problem H index] | punch brush

[LeetCode367 problem effective completely square number] | punch brush

[LeetCode1047 problem delete all adjacent duplicates of the string] | punch brush

[LeetCode160 topic cross linked list] | punch brush

[LeetCode1438 topic absolute difference does not exceed the limit of the longest continuous subarray] | punch brush

[LeetCode434 problem the number of words in a string] | punch brush

[LeetCode75 topic classification of color] | punch brush

[LeetCode513 problem to find the value of the trees left] | punch brush

conclusion

Come on! HXDM!!!!!! 💪 💪 💪

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