給出一個完全二叉樹，求出該樹的節(jié)點個數。
說明：
完全二叉樹的定義如下：在完全二叉樹中披坏，除了最底層節(jié)點可能沒填滿外，其余每層節(jié)點數都達到最大值盐数，并且最下面一層的節(jié)點都集中在該層最左邊的若干位置棒拂。若最底層為第 h 層，則該層包含 1~ 2h 個節(jié)點玫氢。
示例:
輸入:
1
/ \
2 3
/ \ /
4 5 6
輸出: 6
解題思路以及知識點：
- 暴力簡單方法之DFS和BFS遍歷所有結點帚屉，計算節(jié)點數。
- 利用完全二叉樹特殊特點漾峡，減少對所以有節(jié)點的遍歷攻旦。
方法一：BFS或DFS
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
let count=0;
var countNodes = function(root) {
count=0;
dfs(root)
return count;
};
function dfs(root){
if(root===null){
return
}
count++
dfs(root.left)
dfs(root.right)
}
方法二：位操作判斷左右，二分查找尋找最末端節(jié)點生逸。
- 將完全二叉樹的左孩子標記0牢屋，右孩子標記1 如下[1,2,3,4,5,6]節(jié)點。則可將路徑的二進制碼當成當前節(jié)點的編號槽袄，即節(jié)點1為（1）烙无，節(jié)點2為（10），節(jié)點3為（11）遍尺，節(jié)點4為（100）截酷，節(jié)點5為（101），節(jié)點6為（110）以此類推狮鸭，節(jié)點n的路徑可根據n的二進制編碼取得合搅。
- 完全二叉樹特性，可根據深度level確定所有葉子節(jié)點n的取值范圍即：(1<<level)<=n<=(1<<level+1).eg:當level=2時歧蕉，葉子節(jié)點的編號值大于等于4灾部，小于等于7.
- 通過二分查找，尋找葉子節(jié)點的編號之為k惯退。對k的二進制位進行與操作赌髓，根據位的0或1確定路徑向右還是向左。eg：6（110）若判斷判斷二進制第二位的值，則可110&10（6&4）锁蠕，若>0則取右孩子夷野，<0則取左孩子。
- 最終二分查找確定的值即為最后一個葉子節(jié)點荣倾，編號即為節(jié)點個數悯搔。
1(1)
/ \
2(0) 3(1)
/ \ /
4(0) 5(1) 6(0)
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var countNodes = function(root) {
if(root===null){
return 0
}
let level=0,temp=root.left
while(temp){
level++;
temp=temp.left
}
let low=1<<level,high=(1<<level+1)-1,mid
while(low<high){
mid=Math.floor((high-low+1)/2)+low
if(exits(root,level,mid)){
low=mid
}else{
high=mid-1
}
}
return low
};
function exits(root,level,k){
let bit=1<<(level-1),temp=root
while(bit){
if(bit&k){
temp=temp.right
}else{
temp=temp.left
}
bit=bit>>1
}
return temp!==null
}
