Skip to main content

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)

空间复杂度:

O(n)O(n)