Open Tcdian opened 4 years ago
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var countNodes = function(root) {
if (root === null) {
return 0;
}
const leftDepth = countDepth(root.left);
const rightDepth = countDepth(root.right);
if (leftDepth === rightDepth) {
return 1 + countNodes(root.right) + (1 << leftDepth) - 1;
} else {
return 1 + countNodes(root.left) + (1 << rightDepth) - 1;
}
};
function countDepth(patrol) {
let depth = 0;
while(patrol !== null) {
depth++;
patrol = patrol.left;
}
return depth;
}
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function countNodes(root: TreeNode | null): number {
if (root === null) {
return 0;
}
const leftDepth = countDepth(root.left);
const rightDepth = countDepth(root.right);
if (leftDepth === rightDepth) {
return 1 + countNodes(root.right) + (1 << leftDepth) - 1;
} else {
return 1 + countNodes(root.left) + (1 << rightDepth) - 1;
}
};
function countDepth(patrol: TreeNode | null): number {
let depth = 0;
while(patrol !== null) {
depth++;
patrol = patrol.left;
}
return depth;
}
222. Count Complete Tree Nodes
给出一个 完全二叉树,求出该树的节点个数。
Note
完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第
h
层,则该层包含 1~ 2h 个节点。Example