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

Hope is a good thing, maybe the best of things. And no good thing ever dies.

The title

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

Example 1: input: root = [1,null,2,3] output: [1,3,2]Copy the code

Example 2: Input: root = [] Output: [] 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] Output: [1,2]Copy the code

What is middle order traversal?

Middle order traversal (LDR) is a kind of binary tree traversal, also known as middle root traversal, middle order tour. In binary trees, middle-order traversal first traverses the left subtree, then visits the root, and finally traverses the right subtree

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

The problem solving

Use recursion: we traverse the tree the same way we traverse the left subtree — the root node — the right subtree. We traverse the tree the same way we traverse the left subtree or the right subtree until we traverse the entire tree

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

Attached to the reference:

  • Leetcode-cn.com/problems/bi…
  • In the sequence traversal

conclusion

If this article helped you, please like 👍 and follow ⭐️.

If there are any errors in this article, please correct them in the comments section 🙏🙏

Welcome to pay attention to my wechat public number, exchange technology together, wechat search 🔍 : “fifty years later”