145.Binary_Tree_Postorder_Traversal(Easy).md

145. Binary Tree Postorder Traversal (Medium)

Date and Time: May 1, 2025

Link: https://leetcode.com/problems/binary-tree-postorder-traversal

Walk-through:

DFS will have the postorder traversal.

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # Q: Return the postorder traversal: left->right->root
        # S: Run DFS from root
        # TC: O(n), n is total nodes, SC: O(n)

        ans = []
        def dfs(root):
            if not root:
                return
            if root.left:
                dfs(root.left)
            if root.right:
                dfs(root.right)
            ans.append(root.val)
            return
        dfs(root)
        return ans

Time Complexity: $O(n)$
Space Complexity: $O(n)$

Java

/**
 * 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 {
    List<Integer> ans = new ArrayList<>();

    public void dfs(TreeNode node) {
        if (node == null) return;
        if (node.left != null) {
            dfs(node.left);
        }
        if (node.right != null) {
            dfs(node.right);
        }
        ans.add(node.val);
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        // Run DFS on root
        dfs(root);
        return ans;
    }
}