js建树、遍历操作

今天刷js遇到了类似遍历的操作，然后输入是层级遍历的数组，我就开始用js尝试去建树/遍历，突然发现自己太久不打代码变得生疏了，而且js的很多规则我还是不了解。。。码农之路道阻且长。。

首先，二叉树是如下图所示的一个数据结构，

根据层级遍历的数组建树，比如a的索引是0，b是1，c是2；那么左子树节点的索引 l 与根节点的索引i 之间的关系为，l = 2*（i+1）-1；右子树为r = 2*（i+1）；
下面是二叉树节点，第一个利用js里面的函数类型去创建对象，搞得我一头雾水，感觉很奇怪，但是后来用了之后也感觉，其实也一样。
但是有一点需要注意，就是在去实例化这个对象的时候，它必须要new，不然会实例化失败。类似创建数据空间的意思。

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val);
    this.left = (left===undefined ? null : left);
    this.right = (right===undefined ? null : right);
}
1
2
3
4
5

下面的代码是利用深搜、递归去建立二叉树。
dfs深搜，大家可能不太了解，总的来说，就是先一边遍历到底，例如上图所示，他就是遍历A->B->D->E->C->F->G，先把所有左子树遍历完，再去遍历右子树。

var dfs_createTree = function(node,arr,i,node_l =new TreeNode(),node_r =new TreeNode()){

    //利用深搜建树
    var len = arr.length;

    if(2*(i+1)-1<len){
        node_l.val = arr[2*(i+1)-1];
        node.left = dfs_createTree(node_l,arr,2*(i+1)-1);
    }

    if(2*(i+1)<len){
        node_r.val = arr[2*(i+1)];
        node.right = dfs_createTree(node_r,arr,2*(i+1));
    }
    return node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

遇到的问题：
1、刚开始没有return node节点，结果在建树的时候，左右子树都变成了undefined，感觉很奇怪，后来才知道原来是因为自己没有设置返回值。
最后是遍历二叉树：
遍历二叉树，有三种方式，先序（DLR)，中序（LDR），后序（LRD）,L对应左子树，D对应根节点，R对应右子树。
此处是先序遍历。

var dfs_traverse = function(node,result){
    if(node == null) return;
        result.push(node.val);
    dfs_traverse(node.left,result);
    dfs_traverse(node.right,result);
}
1
2
3
4
5
6

遇到问题，创建结果数组，保存遍历结果。

var result = new Array();
1

在这里我用到了array这个对象，他可以用push向数组末尾插入数据，pop删除末尾数据。