【Daily Interview】- 16 遍历二叉树

题目

!! 题目来源：二叉树的前序遍历 - 力扣、二叉树的中序遍历 - 力扣、二叉树的后序遍历 - 力扣

分析

要解决今天的问题，首先要明白什么是前序遍历，什么是中序遍历，什么又是后序遍历。

其实很简单，三者的区别在于遍历节点的顺序，我们以下面的二叉树为例：

三种遍历顺序分别如下：

前序遍历：根 → 左 → 右。上树遍历结果如下：[1, 2, 4, 5, 3, 6, 7]
中序遍历：左 → 根 → 右。上树遍历结果如下：[4, 2, 5, 1, 3, 6, 7]
后续遍历：左 → 右 → 根。上树遍历结果如下：[4, 5, 2, 3, 6, 7, 1]

那么要实现不同的遍历，我们只需要再不同的时候处理节点即可：

// 前序遍历var preorderTraversal = function (root, ary = []) {  if (root !== null) {    ary.push(root.val);    preorderTraversal(root.left, ary);    preorderTraversal(root.right, ary);  }  return ary;};// 中序遍历var inorderTraversal = function(root) {  if (root !== null) {    preorderTraversal(root.left, ary);  ary.push(root.val);    preorderTraversal(root.right, ary);  }  return ary;};// 后续遍历var postorderTraversal = function(root) { if (root !== null) {    preorderTraversal(root.left, ary);    preorderTraversal(root.right, ary);  ary.push(root.val);  }  return ary;};

由此也可以看出三种遍历以及名称的联系。

扩展

也就是说，限制使用递归来遍历树，这里以前序遍历为例（中序和后序思路相同，只是处理节点的位置不同）。

用过调试器的小伙伴都知道有个东西叫函数调用栈，用于记录函数的调用逻辑，当调用函数的时候将函数入栈，返回的时候出栈。而所谓递归就是函数自己调用自己，本质上也是函数调用，所以这里我们可以用借助栈来模拟递归。

在此基础上，如果我们想要完整的遍历一棵树，大致的思路应该如下：

首先令 current 指向当前节点，并将其入栈
随后令 current 指向 current.left
当左子树遍历到头的时候，通过出栈取出上级节点，遍历它的右子树，即令 current 指向 current.right

代码如下：

var preorderTraversal = function (root) {  let current = root;  const treeStack = [];  while (current || treeStack.length > 0) {    while (current) {      treeStack.push(current);      current = current.left;    }    current = treeStack.pop();    current = current.right;  }};

这个时候，再完成前序遍历就很简单了，只需要先处理自己，再处理左右即可：

var preorderTraversal = function (root) {  let current = root;+ const treeNode = [];  const treeStack = [];  while (current || treeStack.length > 0) {    while (current) { +    treeNode.push(current.val);      treeStack.push(current);      current = current.left;    }    current = treeStack.pop();    current = current.right;  }  return treeNode;};

结果如下：

常见问题FAQ

免费下载或者VIP会员专享资源能否直接商用？: 本站所有资源版权均属于原作者所有，这里所提供资源均只能用于参考学习用，请勿直接商用。若由于商用引起版权纠纷，一切责任均由使用者承担。更多说明请参考 VIP介绍。

提示下载完但解压或打开不了？: 最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量，若小于网盘提示的容量则是这个原因。这是浏览器下载的bug，建议用百度网盘软件或迅雷下载。若排除这种情况，可在对应资源底部留言，或联络我们.。

找不到素材资源介绍文章里的示例图片？: 对于PPT，KEY，Mockups，APP，网页模版等类型的素材，文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买，且本站不负责(也没有办法)找到出处。同样地一些字体文件也是这种情况，但部分素材会在素材包内有一份字体下载链接清单。