This is the 14th day of my participation in the August More Text Challenge

Today is the 14th day for me to participate in the August review. Today, I bring you the algorithm problem about binary tree is to find the middle order traversal of binary tree. The text is as follows:

The title

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

Their thinking

Using a recursive

First of all, recursion is the most convenient and efficient way to solve this problem. The middle order traversal of binary tree is as follows: visit the left subtree, visit the root node, visit the right node; Terminates when the current node is empty. Since this problem requires a List array to be returned, the root node is added to the array during recursion, and the contents of the array are the result of middle-order traversal.

Code implementation

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
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;
        }
        // Access the left subtree
        inorder(root.left, res);
        // Access the root node
        res.add(root.val);
        // Access the right subtreeinorder(root.right, res); }}Copy the code

The last

Complexity analysis

  • Time complexity: O(n), where N is the number of nodes in the binary tree. Each node is accessed once and only once in a binary tree traversal.

  • 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.