Subject to a

Leecode 94. Middle-order traversal of binary trees

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

 

Input: root = [1,null,2,3]

Example 2:

Input: root = [] Output: []

Example 3:

Input: root = [1] Output: [1]

Example 4:

Input: root = [1,2] output: [2,1]

Example 5:

Input: root = [1, NULL,2]

Tip:

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

First, we need to understand what middle order traversal of binary trees is: traversal of the tree in the same way that we visit the left subtree — the root node — the right subtree, and traversal of the left subtree or the right subtree in the same way until we have traversed the entire tree. Therefore, the whole traversal process naturally has the nature of recursion, we can directly use recursive function to simulate this process.

Reference code

Define a tree

Struct {* Val int Left *TreeNode // Left * Right *TreeNode // right node *} */Copy the code

GO language version of recursion

func inorderTraversal(root *TreeNode) (res []int) {
	var inorder func(node *TreeNode)
	inorder = func(node *TreeNode) {
		if node == nil {
			return // End the current recursion
		}
		inorder(node.Left) // Click on the bottom left
		res = append(res, node.Val) // Add to array
		inorder(node.Right) // See if there are any branches on the right. If there are, continue. If there are no branches, add the right node to the array
	}
	inorder(root)
	return
}

Copy the code

Iteration stack for GO language version: First in last out

Define a stack, and the stack is a tree

1. First dislike the entire tree, then all the left subtrees

2. Traverse the left subtree, directly to the bottom left

3. I got the bottom left node because I came in and went out

4. Untag objects into arrays

5. Check if there are any left nodes rooted in the right node. If there are, go back to step 1 above.

func inorderTraversal(root *TreeNode) (res []int) {
	stack := []*TreeNode{}    // define a stack that stores a tree
	forroot ! =nil || len(stack) > 0 {
		forroot ! =nil {
			stack = append(stack, root)  // 1. First dislike the entire tree, then all the left subtrees
			root = root.Left   // 2. Traverse the left subtree, directly to the bottom of the left
		}
		root = stack[len(stack)- 1]  // 3. Because of the first in, last out, get the bottom left node
		stack = stack[:len(stack)- 1]
		res = append(res, root.Val) // select * from array
                If yes, go back to step 1. If no, go to step 3
		root = root.Right // 
	}
	return
}

Copy the code

Thank you for reading this, if this article is well written and if you feel there is something to it

Ask for a thumbs up 👍 ask for attention ❤️ ask for share 👥 for 8 abs I really very useful!!

If there are any mistakes in this blog, please comment, thank you very much! ❤ ️ ❤ ️ ❤ ️ ❤ ️