145. 二叉树的后序遍历 | LeetCode算法题解

题目描述

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

示例:

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

思路

其实在算法的世界，二叉树遍历应该是很基础的东西，无论递归还是迭代，不过迭代确实比递归难一点。个人觉得这题归为困难有点过了。

我们用一个栈依次把根，左子树，右子树压入，压左右子树之前把根弹出，记入遍历。由于是后序遍历，所以根的遍历应该在左右子树之后，最后再把遍历结果反转一下就可以了。

解法

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
const postorderTraversal = root => {
  if (!root) return [];

  const result = [];
  const stack = [];
  stack.push(root);

  while (stack.length) {
    const node = stack.pop();
    result.push(node.val);
    if (node.left) {
      stack.push(node.left);
    }
    if (node.right) {
      stack.push(node.right);
    }
  }

  return result.reverse();
};