LeetCode -- Count Complete Tree Node
题目描述：
Given a complete binary tree, count the number of nodes.
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
统计一个完全树的节点数。
完全树的定义是，高度为h+1的树，前h层的每层节点全满。对于第h+1层，没有叶子的节点均在右侧。意味着，不存在左边有些节点没有叶子而右边有些节点有叶子的情况。
实现思路：
递归求左右高度，如果高度相等，直接返回 Math.Pow(2, h) - 1；如果不等，递归求左子树节点数+ 递归求右子树的节点数 + 1;
实现代码：
Given a complete binary tree, count the number of nodes.
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
统计一个完全树的节点数。
完全树的定义是，高度为h+1的树，前h层的每层节点全满。对于第h+1层，没有叶子的节点均在右侧。意味着，不存在左边有些节点没有叶子而右边有些节点有叶子的情况。
实现思路：
递归求左右高度，如果高度相等，直接返回 Math.Pow(2, h) - 1；如果不等，递归求左子树节点数+ 递归求右子树的节点数 + 1;
实现代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int CountNodes(TreeNode root)
{
if(root == null)
{
return 0;
}
var leftH = LeftDepth(root.left);
var rightH = RightDepth(root.right);
if(leftH == rightH){
return (int)Math.Pow(2, leftH + 1) - 1;
}
else{
return CountNodes(root.left) + CountNodes(root.right) + 1;
}
}
public int LeftDepth(TreeNode node){
var h = 0;
while(node != null){
node = node.left;
h++;
}
return h;
}
public int RightDepth(TreeNode node){
var h = 0;
while(node != null){
node = node.right;
h++;
}
return h;
}
}