JAVASCRIPT算法面试

Yangyang 发布于2019-08-21 17:50 / 2211人阅读

摘要：从先序遍历的结果和中序遍历的结果还原二叉树的结构先序遍历结果中序遍历结果，原树中无重复数字考虑了一些特殊情况递归结束的地方根节点的值，根据先序遍历的特点。

自己在网上看到的相关的Javascript算法，持续总结，看别人的算法总觉得很难理解。等自己想不出来的时候就会觉得容易理解了。

二叉树相关，首先是构建二叉树。

从先序遍历的结果和中序遍历的结果还原二叉树的结构,先序遍历结果{1,2,4,7,3,5,6,8},中序遍历结果{4,7,2,1,5,3,8，6},原树中无重复数字

function Node(data,left,right){
    this.data = data;
    this.left = left;
    this.right = right;
    }
  
    function buildBinaryTree(preorder,inorder){
    if(preorder.length!=inorder.length) return null;//考虑了一些特殊情况
    if(preorder.length<0) return null;
    if(preorder.length==1) return new Node(preorder[0],null,null);//递归结束的地方
    var data = preorder[0];//根节点的值，根据先序遍历的特点。
    var root = null;
    var len = preorder.length;
    var index;
    for( index=0 ; index

其次是利用非递归算法来获得二叉树的遍历结果。关键就是用stack来保存树的访问结构。通过pop，push保存访问的顺序，通过node的type来决定是继续分解还是直接输出结果。
function preOrder(root){  //
    if(!root||!root.data) return [];//只是为了区分特殊情况。
    var nodeLeft = [];              //储存要遍历的节点
    nodeLeft.push(root);
    while(nodeLeft.length>0){       
      var node = nodeLeft.pop();
      console.log(node.data);       //先序的话，没必要区分储存的数据是object还是number，因为直接输出就好了。
      if(node.right&&node.right instanceof Node) nodeLeft.push(node.right);          //如果有右节点，那么先存起来，因为要先分析左节点。
      if(node.left&&node.left instanceof Node) nodeLeft.push(node.left);
    }
  }

  function inOrder(root){
    if(!root||!root.data) return [];
    var nodeLeft = [];
    nodeLeft.push(root);
    while(nodeLeft.length>0){
      var node = nodeLeft.pop();
      if(typeof node =="number"){ //data type is number
        console.log(node);
        continue;
      }
      if(node.right&&node.right instanceof Node) nodeLeft.push(node.right); //我觉得对于node的检测应该在node创建的时候完成。
      nodeLeft.push(node.data); //按照遍历顺序存储
      if(node.left&&node.left instanceof Node) nodeLeft.push(node.left);
    }
  }
 

   function postOrder(root){
    if(!root||!root.data) return [];
    var nodeLeft = [];
    nodeLeft.push(root);
    while(nodeLeft.length>0){
      var node = nodeLeft.pop();
      if(typeof node ==="number"){
        console.log(node);
        continue;
      }
      nodeLeft.push(node.data);
      if(node.right&&node.right instanceof Node) nodeLeft.push(node.right);//I think the check for whether this is a qualified node should be done when the node is built.
      if(node.left&&node.left instanceof Node) nodeLeft.push(node.left);
    }
   }

GPU云服务器云服务器 javascript面试自然语言处理算法面试字符串算法面试题面试c语言算法编程题

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/90090.html

Deep in JS - 收藏集 - 掘金

摘要：今天同学去面试，做了两道面试题全部做错了，发过来给道典型的面试题前端掘金在界中，开发人员的需求量一直居高不下。排序算法 -- JavaScript 标准参考教程（alpha） - 前端 - 掘金来自《JavaScript 标准参考教程（alpha）》，by 阮一峰目录冒泡排序简介算法实现选择排序简介算法实现 ... 图例详解那道 setTimeout 与循环闭包的经典面...

enali 2019-08-20 16:36 评论0 收藏0
前端排序算法总结；前端面试题2.0；JavaScript异步编程

摘要：与异步编程按照维基百科上的解释独立于主控制流之外发生的事件就叫做异步。因为的存在，至少在被标准化的那一刻起，就支持异步编程了。然而异步编程真正发展壮大，的流行功不可没。在握手过程中，端点交换认证和密钥以建立或恢复安全会话。 1、前端排序算法总结排序算法可能是你学编程第一个学习的算法，还记得冒泡吗？当然，排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿，面试官在比较...

aaron 2019-08-01 17:38 评论0 收藏0
前端排序算法总结；前端面试题2.0；JavaScript异步编程

摘要：与异步编程按照维基百科上的解释独立于主控制流之外发生的事件就叫做异步。因为的存在，至少在被标准化的那一刻起，就支持异步编程了。然而异步编程真正发展壮大，的流行功不可没。在握手过程中，端点交换认证和密钥以建立或恢复安全会话。 1、前端排序算法总结排序算法可能是你学编程第一个学习的算法，还记得冒泡吗？当然，排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿，面试官在比较...

ARGUS 2019-08-21 16:43 评论0 收藏0
前端排序算法总结；前端面试题2.0；JavaScript异步编程

摘要：与异步编程按照维基百科上的解释独立于主控制流之外发生的事件就叫做异步。因为的存在，至少在被标准化的那一刻起，就支持异步编程了。然而异步编程真正发展壮大，的流行功不可没。在握手过程中，端点交换认证和密钥以建立或恢复安全会话。 1、前端排序算法总结排序算法可能是你学编程第一个学习的算法，还记得冒泡吗？当然，排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿，面试官在比较...

April 2019-08-30 15:53 评论0 收藏0
面试集 - 收藏集 - 掘金

摘要：计算数组的极值微信面试题获取元素的最终前端掘金一题目用代码求出页面上一个元素的最终的，不考虑浏览器，不考虑元素情况。 Excuse me？这个前端面试在搞事！ - 前端 - 掘金金三银四搞事季，前端这个近年的热门领域，搞事气氛特别强烈，我朋友小伟最近就在疯狂面试，遇到了许多有趣的面试官，有趣的面试题，我来帮这个搞事 boy 转述一下。以下是我一个朋友的故事，真的不是我。 ... ja...

crossea 2019-08-20 16:39 评论0 收藏0
JavaScript中的算法（附10道面试常见算法题解决方法和思路）

摘要：中的算法附道面试常见算法题解决方法和思路关注每日一道面试题详解面试过程通常从最初的电话面试开始，然后是现场面试，检查编程技能和文化契合度。值得记住的数组方法有和。一个好的解决方案是使用内置的方法。 JavaScript中的算法（附10道面试常见算法题解决方法和思路）关注github每日一道面试题详解 Introduction 面试过程通常从最初的电话面试开始，然后是现场面试，检查编程...

Cruise_Chan 2019-08-26 10:22 评论0 收藏0