JS-Handwritten/src/arrayToBinaryTree.js at main · HHN0609/JS-Handwritten · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// 参考leetcode的二叉树序列化
// 特别注意这棵树不一定是完全二叉树
// convert [1,2,3,null,null,4,5]
// to
// {
//     val: 1,
//     left: {
//         val: 2,
//         left: null,
//         right: null,
//     },
//     right: {
//         val: 3,
//         left: {
//             val: 4,
//             left: null,
//             right: null,
//         },
//         right: {
//             val: 5,
//             left: null,
//             right: null,
//         }
//     }
// }


/**
 * 迭代实现
 * @param {number[]} arr
 * @return {object}
 */
function arrayToBinaryTree(arr) {
    if(arr[0] === null) return {val: null, left: null, right: null};
    let queue = [];
    let root = {
        val: arr[0],
        left: null,
        right: null
    }
    arr.shift();
    queue.push(root);
    while(queue.length !== 0){
        // 下一层的节点数量
        let nextLevelCount = queue.length * 2;
        let node;
        for(let i=0; i<nextLevelCount; i++){
            let val = arr.shift();
            // 这里不加这个会导致死循环，因为最后一层的节点会一直保存在queue里面
            if(val === undefined){
                return root;
            }
            if(i % 2 === 0) {
                // left child
                node = queue.shift();
                if(val === null) {
                    node.left = null;
                } else {
                    node.left = {
                        val,
                        left: null,
                        right: null,
                    };
                    queue.push(node.left);
                }
            } else {
                // right child
                if(val === null){
                    node.right = null;
                } else {
                    node.right = {
                        val,
                        left: null,
                        right: null,
                    }
                    queue.push(node.right);
                }
            }
        }
    }
    return root;
}
let case1 = [1,2,3,null,null,4,5, 6, null, 7, 8,null];
console.log(arrayToBinaryTree(case1));