关于javascript:JS生成链表和二叉树

最近刷算法题，常常有链表和二叉树的构造，在线运行代码都是间接传入链表或者二叉树的头节点，然而 JS 中没有这样的构造，本地没方法进行调试。明天专门写了下 JS 生成链表和二叉树的办法，下次本地调试就能够间接生成测试用例了。

链表生成

代码如下：

// ListNode 结构器，用于创立链表的每个节点
class ListNode {constructor(val, next) {this.val = (val == undefined ? 0 : val);
        this.next = (next == undefined ? null : next);
    }
}

// 生成链表
function generateLinklist(arr) {let head = new ListNode(arr[0]), // 初始化第一个节点作为头节点
        curr = head; // curr 指针保留以后节点
    for(let i=1; i<arr.length; i++) {curr.next = new ListNode(arr[i]); // 创立 next 节点
        curr = curr.next; // curr 后移一位
    }
    return head // 返回头节点
}

// 调用
const head = generateLinklist([1, 2, 3, 4]);
console.log(head); // 1 -> 2 -> 3 -> 4

实现思路还是比较简单的，然而有一个中央须要留神，curr只能保留以后节点，即下一节点还没创立的时候不能提前挪动。生成链表的办法自己最开始是这样写的：

// 留神，上面这段代码是谬误的
function generateLinklist(arr) {let obj = new Linklist(arr[0]),
        curr = obj.next;
    for(let i=1; i<arr.length; i++) {curr = new Linklist(arr[i]);
        curr = curr.next;
    }
    return obj
}

下面的代码咋一看如同也没问题，然而拿下面用例进行测试的时候发现返回的链表只有一个节点，前面都不见了：

ListNode {val: 1, next: null}

这段代码的问题就在于，curr提前进行挪动了。下面的代码中，先初始化第一个节点 obj 作为头节点，而后 curr = obj.next 的本意是心愿 curr 指向 obj 的下一节点。然而 curr 并没有指向“下一节点”，而是指向了 null，因为下一节点基本还没创立。因为obj.next == null，所以curr = obj.next 相当于curr = null，如下图所示：

这样一来，执行 curr = new Linklist(arr[i]); 的时候，链表的第二个节点的指针其实是赋给了curr，而不是obj.next。

前面每一次 for 循环，都是先将新的节点指针赋给 curr，而后执行curr = curr.next; 将curr的值改为 null，而这些操作都与obj 无关，obj还是最开始那个创立的头节点。

所以从这里得出一个论断，当下一节点还未创立的时候，指针不能提前挪动。在第一段代码中，咱们看到是先创立节点，再挪动 curr 指针的。

二叉树生成