LeetCode -- Count Complete Tree Node

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;








實現代碼：

/**
 * 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;
	}
    
}