145. 二叉树的后序遍历

[buuing]

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

示例给的太简单了, 我们无法从中看出任何规律, 所以这里我增加一个示例

这里通过两条辅助线来展示规律: ACEDB | HIG | F

我发现, 节点的添加顺序是父 -> 右 -> 左进行的unshift操作

• 无脑递归

const postorderTraversal = root => {
  if (!root) return []
  const res = [root.val]
  if (root.right) {
    res.unshift(...postorderTraversal(root.right))
  }
  if (root.left) {
    res.unshift(...postorderTraversal(root.left))
  }
  return res
}

• 迭代 = 栈 + 深度优先搜索

const postorderTraversal = root => {
  if (!root) return []
  const res = [], stack = [root]
  while (stack.length) {
    let curr = stack.pop()
    res.unshift(curr.val)
    curr.left && stack.push(curr.left)
    curr.right && stack.push(curr.right)
  }
  return res
}