count_complete_tree_nodes

hitzzc · hitzzc · commit 7d207fa861ec · 2016-10-17T17:02:01.000+08:00
diff --git a/README.md b/README.md
@@ -175,9 +175,10 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [215. Kth Largest Element in an Array](https://github.com/hitzzc/go-leetcode/tree/master/kth_largest_element_in_an_array)
 #### [216. Combination Sum III](https://github.com/hitzzc/go-leetcode/tree/master/combinations_sum_III)
 #### [217. Contains Duplicate](https://github.com/hitzzc/go-leetcode/tree/master/contains_duplicate)
-#### [218. Contains Duplicate II](https://github.com/hitzzc/go-leetcode/tree/master/contains_duplicate_II)
-#### [219. Contains Duplicate III (unsolved)](https://github.com/hitzzc/go-leetcode/tree/master/contains_duplicate_III)
+#### [219. Contains Duplicate II](https://github.com/hitzzc/go-leetcode/tree/master/contains_duplicate_II)
+#### [220. Contains Duplicate III (unsolved)](https://github.com/hitzzc/go-leetcode/tree/master/contains_duplicate_III)
 #### [221. Maximal Square](https://github.com/hitzzc/go-leetcode/tree/master/maximal_square)
+#### [222. Count Complete Tree Nodes](https://github.com/hitzzc/go-leetcode/tree/master/count_complete_tree_nodes)
 
 
 
diff --git a/count_complete_tree_nodes/count_complete_tree_nodes.cpp b/count_complete_tree_nodes/count_complete_tree_nodes.cpp
@@ -0,0 +1,25 @@
+struct TreeNode {
+	int val;
+	TreeNode *left;
+	TreeNode *right;
+	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
+};
+
+class Solution {
+public:
+	int countNodes(TreeNode* root) {
+		int depth = 0;
+		TreeNode *left, *right;
+		left = right = root; 
+		while (left!=NULL && right!=NULL){
+			left = left->left;
+			right = right->right;
+			++depth;
+		}
+		if (left==NULL && right==NULL)
+			return (1<<depth) - 1;
+		int cnt1 = countNodes(root->left);
+		int cnt2 = countNodes(root->right);
+		return cnt1 + cnt2 + 1;
+	}
+};
