后序非递归遍历

  对树进行后序非递归遍历一般会借助栈来保存路径上的节点。

  后序非递归遍历的一个特点就是:当访问到一个节点时,栈中所保存的节点正好是这个节点的所有祖先节点,因此后续非递归遍历可用来解决以下问题:

  1. 当给定一个节点时,输出该节点的所有祖先
  2. 输出根结点到叶子节点的所有路径
  3. 求每条路径上的节点值之和

  后序非递归遍历的关键点在于判断遍历过程中什么时候该往右走,什么时候该访问节点内容。

  我们使用一个栈来保存遍历路径上的节点,步骤如下:

  1. 一直往左孩子遍历,遍历过程中保存遍历的节点
  2. 当左孩子为空时,我们访问右孩子
  3. 当左右孩子都为空时,我们访问这个节点内容,并返回到父节点
  4. 每当从孩子节点返回父节点时,需要判断是从左孩子返回的还是从右孩子返回的,若是从左孩子返回的,我们需要继续访问右孩子,而若是从右孩子返回的,我们则访问当前节点,并返回到其父节点。

  判断一次返回是否是从右孩子返回,我们可以使用一个变量 t,当一个节点返回时,我们使用 t 记录这个节点,在父节点处判断 t 是否与这个节点的右孩子相等,若相等,则说明是从右孩子返回的,否则就是从左孩子返回的。

JS 代码:

int* postorderTraversal(root){
    let stack = [];
    let node = root, r = null;

    while (node || stack.length) {
        // 一路往左走
        while (node) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();

        // 左走到底时,若有右孩子且当前不是从右孩子返回,那么访问右孩子
        // PS:当从右孩子返回时后序遍历就该访问当前节点了
        if (node.right && node.right !== r) {
            stack.push(node);   // 注意:这里需要保存父节点,否则进入右孩子后父节点就消失了!!
            node = node.right;
        } else {
            // 在这边访问节点值!

            // 每次返回到父节点时都使用 r 记录,后面可以用来判断是否是从右孩子返回的
            r = node;
            node = null;
        }
    }

    return root;
}

morris 算法遍历节点值

  若需要使用非递归算法后序遍历节点值,那么可使用 morris 算法实现 O(1) 复杂度的遍历。

具体可看:使用Morris算法进行后序非递归遍历


 目录