描述

给出一个二叉树，要求输出它的前序遍历、中序遍历、后序遍历和层序遍历。

思路

前序遍历：根左右。
中序遍历：左根右。
后序遍历：左右根。
层序遍历：从上到下、从左到右，数组的每一行为二叉树的一层。
前序、中序、后序思路是一样的，只是入栈顺序的不同，递归即可。
层序遍历则需要使用队列，将当前层的节点入队，再处理队列中的本层节点，完成后将结果存入数组即可。

代码

前序、中序、后序遍历

function postorder(list, node) {
  if (!node) {
    return;
  }
  // 只需要改变这里的代码顺序即可实现不同的遍历方式，此处为后序
  postorder(list, node.left);
  postorder(list, node.right);
  list.push(node.val);
}
function postorderTraversal(root) {
  let list = new Array();
  postorder(list, root);
  return list;
}

层序遍历

function levelOrder(root) {
  // 初始化结果数组
  let res = new Array();
  if (!root) return res;
  // 初始化辅助队列
  let que = new Array();
  que.push(root);
  while (que.length) {
    let len = que.length;// 取出当前层的节点数
    // 保存本层的节点
    let curLevel = new Array();
    // 只遍历当前层的节点
    while (len--) {
      // 队列先进先出保证顺序
      let node = que.shift();
      curLevel.push(node.val);// 保存当前节点数据
      if (node.left) que.push(node.left);// 左孩子入队
      if (node.right) que.push(node.right);// 右孩子入队
    }
    if (curLevel.length) res.push(curLevel);// 保存当前层结果
  }
  return res;
}

本文作者：TTQ
本文链接：https://blog.ponder.fun/archives/150.html
最后修改时间：2022-04-26 22:02:11
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！