风动之石的博客

二叉树

找出二叉树中所有节点的个数

节点结构如下，请补充countsNodes函数

function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}

function countsNodes(root) {

}
1
2
3
4
5
6
7
8

参考答案：

1、递归

function countsNodes(root) {
    if (!root) {
        return 0;
    }
    return 1 + countsNodes(root.left) + countsNodes(root.right);
}
1
2
3
4
5
6

2、迭代

function countsNodes(root) {
    let sum = 0;
    const arr = [root];

    while (arr.length) {
        const node = arr.shift();
        if (node.left) {
            arr.push(node.left);
        }

        if (node.right) {
            arr.push(node.right);
        }
        sum++;
    }

    return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

或者

function countsNodes(root) {
    let sum = 0;
    const arr = [root];

    for (let i = 0; i < arr.length; i++) {
        const node = arr[i];
        if (node) {
            sum++;
            if (node.left) {
                arr.push(node.left);
            }
            if (node.right) {
                arr.push(node.right);
            }
        } else {
            break;
        }
    }

    return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21