摘要：重建二叉樹輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹。所以先通過前序遍歷找出根節(jié)點(diǎn)，然后將中序遍歷分為左右子樹兩組，最后對(duì)于每個(gè)子樹依次遞歸調(diào)用。

重建二叉樹

輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。

思路：二叉樹前序遍歷第一個(gè)點(diǎn)為根節(jié)點(diǎn)，中序遍歷順序?yàn)橄茸笞訕淙缓蟾?jié)點(diǎn)最后右子樹。所以先通過前序遍歷找出根節(jié)點(diǎn)，然后將中序遍歷分為左右子樹兩組，最后對(duì)于每個(gè)子樹依次遞歸調(diào)用。

function TreeNode(x) {
????this.val = x;
????this.left = null;
????this.right = null;
}
//pre為前序遍歷序列數(shù)組 vin為中序遍歷序列數(shù)組
function reConstructBinaryTree(pre, vin){
  if(pre.length == 0 || vin.length == 0) {
    return null;
  }
  let root = new TreeNode(pre[0]);
  //根節(jié)點(diǎn)在中序遍歷中的位置
  let index = vin.indexOf(pre[0]);
  let leftPre = pre.slice(1,index+1);//前序左子樹
  let rightPre = pre.slice(index+1);//前序右子屬
  let leftVin = vin.slice(0,index);//中序左子樹
  let rightVin = vin.slice(index+1);//中序右子樹
  //開始遞歸
  root.left = reConstructBinaryTree(leftPre,leftVin);
  root.right = reConstructBinaryTree(rightPre,rightVin);
  return root;
}

console.log(reConstructBinaryTree([1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]));

二叉樹的下一個(gè)節(jié)點(diǎn)

給定一個(gè)二叉樹和其中的一個(gè)結(jié)點(diǎn)，請(qǐng)找出中序遍歷順序的下一個(gè)結(jié)點(diǎn)并且返回。注意，樹中的結(jié)點(diǎn)不僅包含左右子結(jié)點(diǎn)，同時(shí)包含指向父結(jié)點(diǎn)的指針。

思路：根據(jù)中序遍歷的特點(diǎn)，要找到一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)無(wú)非就是三種情況：1、有右子樹，這時(shí)只需要把其右孩子作為下一個(gè)遍歷的（并不是要找的）節(jié)點(diǎn)，然后沿著該節(jié)點(diǎn)的左子樹（如果有的話）出發(fā)，直到遇到葉子節(jié)點(diǎn)，那么該葉子節(jié)點(diǎn)就是其下一個(gè)要找的節(jié)點(diǎn)；2、沒有右子樹，則判斷該節(jié)點(diǎn)是否是其父節(jié)點(diǎn)的左孩子，如果是則其下一個(gè)要找的節(jié)點(diǎn)是其父節(jié)點(diǎn)；3、如果不是其父節(jié)點(diǎn)的左孩子，則把其父節(jié)點(diǎn)作為下一個(gè)遍歷的節(jié)點(diǎn)，向上回溯，直到找到父節(jié)點(diǎn)沒有父節(jié)點(diǎn)并且父節(jié)點(diǎn)是父節(jié)點(diǎn)的父節(jié)點(diǎn)的左孩子為止。綜合這三種情況就可以找到二叉樹中任意一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。

function TreeNode(x) {
????this.val = x;
????this.left = null;
????this.right = null;
    this.parent = null;
}
function getNext(node) {
  let curNode = null;
  //第一、判斷是否有右孩子
  if(node.right != null) {
    curNode = node.right;
    while(curNode.left !=null) {
      curNode = curNode.left;
    }
    return curNode;
  }
  //第二、判斷是否是其父節(jié)點(diǎn)的左孩子
  if(node.parent == null) {
    return null;
  }
  if(node.parent.left == node) {
    return node.parent;
  }
  //第三、向上找其父節(jié)點(diǎn)，直到父節(jié)點(diǎn)是其父節(jié)點(diǎn)的父節(jié)點(diǎn)的左孩子
  curNode = node.parent;
  while(curNode.parent != null) {
    if(curNode == curNode.parent.left) {
      return curNode.parent;
    }
    curNode = curNode.parent;
  }
  return null;
}

//構(gòu)建二叉樹
let parentNode = createTree(
  ["a","b","d","e","h","i","c","f","g"],
  ["d","b","h","e","i","a","f","c","g"]);

let i = parentNode.left.right.right;//i節(jié)點(diǎn)
let b = parentNode.left;//b節(jié)點(diǎn)
let f = parentNode.right.left;//f節(jié)點(diǎn)
console.log(getNext(i).val);//a
console.log(getNext(b).val);//h
console.log(getNext(f).val);//c

//根據(jù)前序遍歷和中序遍歷構(gòu)建一顆二叉樹
function createTree(pre,vin){
  function TreeNode(x) {
  ????this.val = x;
  ????this.left = null;
  ????this.right = null;
      this.parent = null;
  }
  //pre為前序遍歷序列數(shù)組 vin為中序遍歷序列數(shù)組
  function reConstructBinaryTree(pre, vin,parent){
    if(pre.length == 0 || vin.length == 0) {
      return null;
    }
    let root = new TreeNode(pre[0]);
    //根節(jié)點(diǎn)在中序遍歷中的位置
    let index = vin.indexOf(pre[0]);
    let leftPre = pre.slice(1,index+1);//前序左子樹
    let rightPre = pre.slice(index+1);//前序右子屬
    let leftVin = vin.slice(0,index);//中序左子樹
    let rightVin = vin.slice(index+1);//中序右子樹
    //開始遞歸
    root.parent = parent;
    root.left = reConstructBinaryTree(leftPre,leftVin,root);
    root.right = reConstructBinaryTree(rightPre,rightVin,root);
    return root;
  }

  return reConstructBinaryTree(pre,vin,null);
}