2019-06-19

二叉树遍历递归和非递归

假如二叉树的定义为

function Tree(val) {
  this.val = val;
  this.left = this.right = null;
}

二叉树遍历的递归实现方式非常简洁易懂，通过函数调用栈保存了遍历到的节点，当函数返回时，我们很容易知道从哪一个节点开始继续遍历。

pre-order遍历的递归实现

function traverse(tree) {
  if (!tree) return;
  console.log(tree.val);
  if (tree.left) traverse(tree.left);
  if (tree.right) traverse(tree.right);
}

调用traverse(tree.left)会先保存当前函数的局部变量，参数，然后在函数调用栈中创建一个frame，新的frame记录了traverse(tree.left)返回时，下一步要执行的代码的地址，在这里应该是 if (tree.right) traverse(tree.right);

用stack模拟递归调用

所有递归形式的程序都有等价的非递归的形式。把递归形式的程序转换为非递归的形式的思路是，用一个stack来模拟函数调用栈，每个递归调用相当于一个push操作，函数返回相当于pop操作。我们push到栈上的数据需要至少提供两种信息，执行push操作时的上下文和执行pop以后要执行的代码。

对于pre-order遍历来说，push到栈上的数据需要至少提供两个信息，一是push到栈的节点的父节点，二是push到栈的节点是左节点还是右节点，当然更完善的模拟应该把所有局部变量、参数都保存在堆栈中。有了这两个信息，我们就可以在pop以后，区别开这个pop模拟的是一次traverse(tree.left)返回了，还是traverse(tree.right)返回了。之所以要知道这一点，一是为了决定是否打印节点，二是为了判断下一个遍历的节点是哪一个。如果是traverse(tree.right)返回了，那么程序就结束了；如果是traverse(tree.left)结束了，那么还要继续遍历右节点。

pre-order非递归实现

function traverse(tree) {
  if (!tree) return;
  let stack = [{
    tree: tree,
    parent: null, // 父节点，通过父节点可以拿到右节点
    isLeft: true // 是左节点，还是右节点
  }];
  while (stack.length > 0) {
    let node = stack[stack.length-1];
    console.log(node.tree.val); // pre-order遍历先打印父节点

    if (node.tree.left) {
		  // pre-order先遍历左节点，push相当于一次递归调用traverse(tree.left);
      stack.push({
        tree: node.tree.left,
        parent: node.tree,
        isLeft: true
      });
    } else if (node.tree.right) {
		  // 如果最左边的节点没有左节点了，那么遍历右节点，相当于调用traverse(tree.right);
      stack.push({
        tree: node.tree.right,
        parent: node.tree,
        isLeft: false
      });
    } else {
		  // 到达叶子节点，相当于递归版本中if (!tree) return;
			// 开始pop，模拟函数返回
			// 这里就用到了保存在堆栈上的parent和isLeft信息
			// 利用这两个信息可以判断当前的pop是否相当于traverse(tree.left)返回
			// 如果是，那么需要遍历右节点，否则继续pop(相当于返回到上层函数)
      while (stack.length > 0){
        let top = stack.pop();
        if (top.isLeft && top.parent && top.parent.right) {
          stack.push({
            tree: top.parent.right,
            parent: top.parent,
            isLeft: false
          });
          break;
        } 
      }
    }
  }
}

这里我们使用堆栈模拟了函数递归调用过程，基本的流程是，一开始连续地入栈，模拟函数调用，然后出栈，判断是否要遍历右节点，然后重复这个过程。这段代码还是比较复杂的，不怎么直观，下面的代码更简洁。

function traverse(tree) {
  if (!tree) return;
  let stack = [tree];
  while (stack.length > 0) {
    let node = stack.pop();
    console.log(node.val);
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
}

为什么代码可以精简成这样呢?主要是两点，因为是pro-order遍历，先打印父节点，这样在后面的程序中没必要保留对父节点的引用。二是左子树遍历完，下一个节点就是右节点，我们不必等到遍历左子树完成就可以把右节点先放到堆栈中。同样对于遍历左子树，当打印完左子树根节点，就没必要保留对根节点的引用了。因此上面这段程序从堆栈中pop一个节点，就马上打印。而模拟堆栈版本的程序，堆栈中一直保留着从根节点到叶子节点的引用，直到从叶子节点开始pop，因为这样才完整模拟了函数调用。

对比上面的两段非递归pre-order遍历代码，我们发现模拟函数调用写出的代码其实会比较复杂，还需要经过优化才更容易理解。

in-order遍历

递归实现

function traverse(tree) {
  if (!tree) return;
  if (tree.left) traverse(tree.left);
  console.log(tree.val);
  if (tree.right) traverse(tree.right);
}

非递归实现

function traverse(tree) {
  if (!tree) return;
  let stack = [tree];
  while (stack.length > 0) {
    let top = stack[stack.length-1];
    if (top.left) {
      stack.push(top.left);
    } else {
      while (stack.length > 0) {
        top = stack.pop();
        console.log(top.val);
        if (top.right) {
          stack.push(top.right);
          break;
        }
      }
    }
  }
}

post-order遍历

递归实现

function traverse(tree) {
  if (!tree) return;
  if (tree.left) traverse(tree.left);
  if (tree.right) traverse(tree.right);
  console.log(tree.val);
}

非递归实现

function traverse(tree) {
  if (!tree) return;
  let stack = [tree];
  let revStack = [];
  while (stack.length > 0) {
    let top = stack.pop();
    revStack.push(top);
    if (top.left) stack.push(top.left);
    if (top.right) stack.push(top.right);
  }

  while (revStack.length > 0) {
    let top = revStack.pop();
    console.log(top.val);
  }
}

post-order的非递归遍历比较有意思。我们观察到post-order的遍历顺序是，左-右-中，而如果pre-order遍历的时候先右后左遍历，那么遍历顺序是中-右-左，刚好和post-order的顺序相反，我们把这种遍历顺序叫reverse-pre-order。因此如果想得到post-order的遍历，那么可以按照reverse-pre-order遍历，然后把遍历到的节点依次放到另外一个堆栈中，最后把这个堆栈中的内容输出，就是post-order的遍历。

上图post-order的顺序是2, 3, 1, 5, 7, 6, 4，而reverse-pre-order的顺序刚好是4，6，7，5，1，3，2。