94. Binary Tree Inorder Traversal Easy

Given the root of a binary tree, return the inorder traversal of its nodes' values.

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

Example 2:
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,2,6,5,7,1,3,9,8]

Example 3:
Input: root = []
Output: []

Approach

Input: The root node of a binary tree root.

Output: Return the inorder traversal of node values.

This problem belongs to Binary Tree Traversal problems.

The order of inorder traversal is: Left Subtree → Root Node → Right Subtree.

We can define a recursive depth-first traversal function dfs. After recursively traversing the left subtree, we record the current node's value, and then continue traversing the right subtree, thus implementing an inorder traversal.

Implementation

python

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # Used to store the traversal results
        res = []

        # Define the recursive function for inorder traversal: Left -> Root -> Right
        def dfs(node: Optional[TreeNode]):
            if node is None:
                return

            dfs(node.left)           # Recursively traverse left subtree
            res.append(node.val)     # Record the current node
            dfs(node.right)          # Recursively traverse right subtree

        # Start traversal from the root node
        dfs(root)

        return res

javascript

/*
 * @param {TreeNode} root
 * @return {number[]}
 */
const inorderTraversal = function(root) {
    // Used to store the traversal results
    const res = [];

    // Define the recursive function for inorder traversal: Left -> Root -> Right
    function dfs(node) {
        if (!node) return;

        // Recursively traverse left subtree
        dfs(node.left);
        // Record the current node
        res.push(node.val);
        // Recursively traverse right subtree
        dfs(node.right);
    }

    dfs(root);
    return res;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(h), where h is the height of the tree

Links

94. Binary Tree Inorder Traversal (English)

94. 二叉树的中序遍历 (Chinese)