JAVASCRIPT算法面試

Yangyang 發(fā)布于2019-08-21 17:50 / 2312人閱讀

摘要：從先序遍歷的結(jié)果和中序遍歷的結(jié)果還原二叉樹的結(jié)構(gòu)先序遍歷結(jié)果中序遍歷結(jié)果，原樹中無重復(fù)數(shù)字考慮了一些特殊情況遞歸結(jié)束的地方根節(jié)點(diǎn)的值，根據(jù)先序遍歷的特點(diǎn)。

自己在網(wǎng)上看到的相關(guān)的Javascript算法，持續(xù)總結(jié)，看別人的算法總覺得很難理解。等自己想不出來的時(shí)候就會(huì)覺得容易理解了。

二叉樹相關(guān)，首先是構(gòu)建二叉樹。

從先序遍歷的結(jié)果和中序遍歷的結(jié)果還原二叉樹的結(jié)構(gòu),先序遍歷結(jié)果{1,2,4,7,3,5,6,8},中序遍歷結(jié)果{4,7,2,1,5,3,8，6},原樹中無重復(fù)數(shù)字

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);//遞歸結(jié)束的地方
    var data = preorder[0];//根節(jié)點(diǎn)的值，根據(jù)先序遍歷的特點(diǎn)。
    var root = null;
    var len = preorder.length;
    var index;
    for( index=0 ; index

其次是利用非遞歸算法來獲得二叉樹的遍歷結(jié)果。關(guān)鍵就是用stack來保存樹的訪問結(jié)構(gòu)。通過pop，push保存訪問的順序，通過node的type來決定是繼續(xù)分解還是直接輸出結(jié)果。
function preOrder(root){  //
    if(!root||!root.data) return [];//只是為了區(qū)分特殊情況。
    var nodeLeft = [];              //儲(chǔ)存要遍歷的節(jié)點(diǎn)
    nodeLeft.push(root);
    while(nodeLeft.length>0){       
      var node = nodeLeft.pop();
      console.log(node.data);       //先序的話，沒必要區(qū)分儲(chǔ)存的數(shù)據(jù)是object還是number，因?yàn)橹苯虞敵鼍秃昧恕?      if(node.right&&node.right instanceof Node) nodeLeft.push(node.right);          //如果有右節(jié)點(diǎn)，那么先存起來，因?yàn)橐确治鲎蠊?jié)點(diǎn)。
      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); //我覺得對(duì)于node的檢測(cè)應(yīng)該在node創(chuàng)建的時(shí)候完成。
      nodeLeft.push(node.data); //按照遍歷順序存儲(chǔ)
      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);
    }
   }