JS重建二叉树

2018-05-16

重建二叉树的前置知识：

1. 遍历二叉树：

（1）前序遍历：根左右 –> 先访问根节点，再前序遍历左子树，最后前序遍历右子树；

（2）中序遍历：左根右 –> 先中序遍历左子树，再访问根节点，最后中序遍历右子树。

（3）后序遍历：左右根 –> 先后序遍历左子树，再后序遍历右子树，组后访问根节点。

2. 重建二叉树：

（1）前序+中序：前序遍历序列和中序遍历序列可以确定唯一的二叉树

 function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
function reConstructBinaryTree(pre, vin)
{
    if(pre.length === 0 || vin.length === 0){
        return null;
    }
    //创建根节点，根节点是前序遍历的第一个数
    var root = pre[0];
    var tree = new TreeNode(root);
    //找到中序遍历根节点所在位置
    var index = vin.indexOf(root);
    //对于中序遍历，根节点左边的节点即左子树，根节点右边的节点即右子树
    tree.left = reConstructBinaryTree(pre.slice(1,index+1),vin.slice(0,index));
    tree.right = reConstructBinaryTree(pre.slice(index+1),vin.slice(index+1));
    return tree;
}
测试：
pre='abdecf'
vin='dbeacf'
t=reConstructBinaryTree(pre,vin)
console.log(t);
输出：
TreeNode {
  val: 'a',
  left: 
   TreeNode {
     val: 'b',
     left: TreeNode { val: 'd', left: null, right: null },
     right: TreeNode { val: 'e', left: null, right: null } },
  right: 
   TreeNode {
     val: 'c',
     left: null,
     right: TreeNode { val: 'f', left: null, right: null } } }
[Finished in 0.9s]

（2）中序+后序：中序遍历序列和后序遍历序列可以确定唯一的二叉树

 function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
function reConstructBinaryTree(pos, vin)
{
    if(!pos || vin.length === 0){
        return null;
    }
    //创建根节点，根节点是后序遍历的最后一个数
    var root = pos[pos.length-1];
    var tree = new TreeNode(root);
    //找到中序遍历根节点所在位置
    var index = vin.indexOf(root);
    //对于中序遍历，根节点左边的节点即左子树，根节点右边的节点即右子树
    tree.left=reConstructBinaryTree(pos.slice(0,index),vin.slice(0,index))
    tree.right=reConstructBinaryTree(pos.slice(index,pos.length-1),vin.slice(index+1))
    return tree;
}
测试：
vin='dbeacf'
pos='debfca'
p=reConstructBinaryTree(pos,vin)
console.log(p);
输出：
TreeNode {
  val: 'a',
  left: 
   TreeNode {
     val: 'b',
     left: TreeNode { val: 'd', left: null, right: null },
     right: TreeNode { val: 'e', left: null, right: null } },
  right: 
   TreeNode {
     val: 'c',
     left: null,
     right: TreeNode { val: 'f', left: null, right: null } } }
[Finished in 0.6s]