Binary Tree Postorder Traversal

Description

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

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

 

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

Solution(javascript)

/*
 * @lc app=leetcode id=145 lang=javascript
 *
 * [145] Binary Tree Postorder Traversal
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/** none recursive
 * @param {TreeNode} root
 * @return {number[]}
 */
const postorderTraversal = function (root) {
  const stack = []
  const result = []
  const push = (node) => {
    if (node) {
      stack.push(node)
    }
  }
  const pop = () => {
    while (stack.length > 0) {
      const node = stack.pop()
      result.push(node.val)
      push(node.left)
      push(node.right)
    }
  }
  push(root)
  pop()
  return result.reverse()
}