本文共 1779 字，大约阅读时间需要 5 分钟。

1.先序&&中序

（1）根据给出的层次遍历建立二叉树

function TreeNode(val){  this.val = val;  this.left = null;  this.right = null;}function  createTreeByLevelOrder(levelOrder){  let queue = []   // queue 里面存储的是新建的树的层序遍历的节点关系  // queue中是两层节点之间的父子关系  if(levelOrder[0]){    let node = levelOrder.shift()    var root = new TreeNode(node)    queue.push(root)    while(queue.length && levelOrder.length){      // 只有在levelOrder的元素不为null的时候，才会新建节点，然后向queue中push，所以用queue.length作为循环判断      // 使用levelOrder.length来判断是否有剩余节点，不管最后一个节点之后是否填充null，都可以；如果最后节点之后没有填充null的话，防止死循环      let par = queue.shift()      let pleft = levelOrder.shift()      if(pleft !== null){        par.left = new TreeNode(pleft)        queue.push(par.left)      }            let pright = levelOrder.shift()      if(pright !== null){        par.right = new TreeNode(pright)        queue.push(par.right)      }    }  }  return root}

（2）中序&&先序

function pre(root){    if(root){      preArr.push(root.val)      pre(root.left)      pre(root.right)    }  }  function In(root){    if(root){      In(root.left)      inArr.push(root.val)      In(root.right)    }  }  const preArr = []  const inArr = []  pre(root)  In(root)  let l = inArr.indexOf(p)  let r = inArr.indexOf(q)  const set = new Set(inArr.slice(l, r+1))  for(let el of preArr){    if(set.has(el)) return el  }

2.map记录每个节点的祖先节点

function pre(root){  if(root){    if(root.left){      map.set(root.left.val, [root.left.val, ...map.get(root.val)])    }    if(root.right){      map.set(root.right.val, [root.right.val, ...map.get(root.val)])    }    pre(root.left)    pre(root.right)  }}const map = new Map()map.set(root.val, [root.val])mappre(root)mapconst set1 = new Set(map.get(5)) const set2 = new Set(map.get(1))set1set2for(el of set1){  if(set2.has(el)){    console.log(el);    break;  }}

转载地址：http://wkxzi.baihongyu.com/