LeetCode Q222: Count Complete Tree Nodes

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.

Solution 1:
先看左右两路径的高度是否一样，如果一样，直接计算节点数目， 如果不一样，在递归。

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	int countNodes(TreeNode* root) {
	if(root==NULL)
	return 0;
	int nl=0, nr=0;
	TreeNode* l=root, *r=root;
	while(l!=NULL){
	nl++;
	l=l->left;
	}
	while(r!=NULL){
	nr++;
	r=r->right;
	}
	if(nl==nr)
	return pow(2, nl)-1;
	return 1+countNodes(root->left)+countNodes(root->right);
	}
	};

view raw Q222countcompleteTreeNodes.cpp hosted with ❤ by GitHub

Solution 2:
calculate height of right tree, if the same as height, go to right tree(append 1 to binary result), otherwise go to left tree (Append 0 to binary result)

	int countNodes(TreeNode* root)
	{
	int result,height,RTreeHeight;
	TreeNode* visit,*p;
	if (root==NULL) return 0;
	p = visit = root;
	height = 0;
	for(;p;p = p -> left) height++;
	result = 1;
	while(--height)
	{
	result <<= 1;
	RTreeHeight = 0;
	p = visit->right;
	for(;p;p = p -> left) RTreeHeight++;
	if (RTreeHeight < height) visit = visit->left;
	else
	{
	result |= 1;
	visit = visit->right;
	}
	}
	return result;
	}

view raw Q222-2.cpp hosted with ❤ by GitHub