LeetCode Notes: Binary Tree Postorder Traversal

#leetcode

Question

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 = []

Output: []

Example 3:

Input: root = [1]

Output: [1]

Example 4:

Input: root = [1,2]

Output: [2,1]

Example 5:

Input: root = [1,null,2]

Output: [2,1]

Constraints:

  • The number of the nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

Solution

Analysis:

Recursively visit the left subtree, right subtree, and root node of the binary tree, and store them in an array.

Code:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 * this.val = (val===undefined? 0: val)
 * this.left = (left===undefined? null: left)
 * this.right = (right===undefined? null: right)
 *}
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function (root) {
  // Special case
  if (root == null) return [];

  // Recursively, to access the left subtree, right subtree, root node, and store the node value in the array
  function postOrder(node, result = []) {
    if (node != null) {
      postOrder(node.left, result);
      postOrder(node.right, result);
      result.push(node.val);
    }
  }
  // Create a new array for storing the results and start recursively traversing the entire binary tree
  const result = [];
  postOrder(root, result);
  return result;
};

Reference

Comments