This is the 16th day of my participation in the First Challenge 2022

Recommended reading

  • CSDN home page
  • GitHub open source address
  • Unity3D plugin sharing
  • Jane’s address book
  • My personal blog
  • QQ group: 1040082875

Hello, everyone, I am a little Magic dragon, Unity3D software engineer, VR, AR, virtual simulation direction, update software development skills from time to time, life perception, remember to use one button three links.

A, the title

1. Algorithm topic

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

Title link:

Source: LeetCode

Link: 94. Middle Order Traversal of binary Trees – LeetCode (leetcode-cn.com)

2

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: []Copy the code

Second, the problem solving

1. Analysis of ideas

First, understand what is the middle order traversal of a binary tree, which is to traverse the tree in the same way as accessing the left subtree → the root node → the right subtree.

The traversal process is a recursive process, so you can use recursive functions to simulate this process.

2. Code implementation

Code reference:

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

    public void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        inorder(root.left, res);
        res.add(root.val); inorder(root.right, res); }}Copy the code

3. Time complexity

Time complexity: O(n)

Where n is the number of nodes in the binary tree. Each node traversed through the binary tree is accessed only once.

Space complexity: O(n)

The spatial complexity depends on the stack depth of the recursion, which is O(n) in the case of a binary tree as a chain.

Third, summary

Recursive algorithms, the thing to notice is the condition for recursion, and the condition for ending recursion.

Recursion: first to the root, then to the left subtree, then to the right subtree. Each subtree recurses.