【牛客】二叉树的遍历
浏览 181 | 评论 0 | 字数 1144
TTQ
2022年04月24日
  • 描述

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

    思路

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

    代码

    前序、中序、后序遍历

    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 授权协议,转载请注明来源,谢谢!
    评论
    与本文无关评论请发留言板。请不要水评论,谢谢。
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论