leetcode 222 Count Complete Tree Nodes （计算完全二叉树节点

1. 问题描述

　　计算完全二叉树的节点数。对于完全二叉树的定义可参考上面的内容。

2. 方法与思路

　　最简单也最容易想到的方法就是使用递归，，分别递归计算左右子树的节点数的和。但此方法最容易超时，一般不可取。 　　

int countNodes(TreeNode* root) {;) return 1;return countNodes(root->left) + countNodes(root->right);}

　　用这段代码提交，果真还是超时了。那么如何改进呢？ 　　那就是利用满二叉树来简化算法。满二叉树的节点数计算公式为N = 2^h – 1. h为二叉树的层数。递归过程如下： 　　

判断以当前节点为根节点的数是否为满二叉树，若是计算节点个数并返，回否则继续往下执行。对当前节点的左子树和右子树分别判断，并加一，表示该节点计数。/** * 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:l=1,r=1;TreeNode *node = root;while(node->left){l++;node = node->left;}node = root;while(node->right){r++;node = node->right;}if(l == r)return (int)pow(2,(double)l) – 1;;}int countNodes(TreeNode* root) {if(root == NULL) return 0;//else if(root->left == NULL) return 1;if(nodesofMan(root)) return nodesofMan(root);elsereturn countNodes(root->left) + countNodes(root->right) +1;}};

其实，每个人都是幸福的。只是，你的幸福，常常在别人眼里。