145. 二叉树的后序遍历

题目链接

145. 二叉树的后序遍历

迭代方法

使用迭代的方式完成后序遍历。通过定义一个变量prev记录上一个遍历的节点来判断右边子树是否已经遍历。

解题方法

1. 在stack非空而且root不是null的情况下循环
2. 如果root存在左子树，则不断地将左子树压入栈中
3. 将栈顶的元素node取出，判断是否存在右子树或者右子树是否已经遍历
4. 如果prev等于node，那么右子树已经遍历。
5. 如果第三条成立，那么：
   1. 访问该节点，result.push(node.val)
   2. prev = node
   3. root = null，表示该树已经完成遍历，继续从栈顶获取node。
6. 如果第三条不成立，那么重新将节点压入栈中，并且开始遍历右子树，因为要遍历右子树之后再访问根节点。

代码

/**
 * 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) {
  const result = [];
  let prev = null;
  const stack = [];

  while(stack.length || root) {
    while(root) {
      stack.push(root);
      root = root.left;
    }
    node = stack.pop();
    if(node.right === null || prev === node.right) {
      result.push(node.val);
      prev = node;
      root = null;
    } else {
      // 继续将root压入栈中并遍历右边子树
      stack.push(node);
      root = node.right;
    }
  }
  return result;
};

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(n)$