145. Binary Tree Postorder Traversal Easy

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

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

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

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

Approach

Input: The root node of a binary tree root.

Output: Return the postorder traversal of its nodes' values.

This problem belongs to Binary Tree Traversal problems.

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

We can define a recursive depth-first traversal function dfs. We record the value of the current node after recursively traversing the right subtree, thus implementing postorder traversal.

Implementation

python

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

        # Define a recursive function to perform postorder traversal: Left -> Right -> Root
        def dfs(node: Optional[TreeNode]):
            if node is None:
                return

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

        # Start traversal from the root node
        dfs(root)

        return res

javascript

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

    // Define a recursive function to perform postorder traversal: Left -> Right -> Root
    function dfs(node) {
        if (!node) return;

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

    // Start traversal from the root node
    dfs(root);

    return res;
};

Complexity Analysis

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

Links

145. Binary Tree Postorder Traversal (English)

145. 二叉树的后序遍历 (Chinese)