[itint5]完全二叉树节点个数的统计 - 阿牧遥 - 博客园
这题是利用完全二叉树的性质计算节点数目。那么是通过比较左右子树的最左结点的高度来看那边是满的，然后递归计算。
给定一棵完全二叉树的根结点，统计该树的结点总数。
树结点类型名为TreeNode，您没必要知道该类型的定义，请使用下面的方法得到某个结点的左，右儿子结点，以及判断某结点是否为NULL。
https://github.com/AnnieKim/ITint5/blob/master/004_%E7%BB%9F%E8%AE%A1%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%BB%93%E7%82%B9%E6%95%B0.cpp
//获得结点node的左儿子结点
TreeNode getLeftChildNode(TreeNode node);
//获得结点node的右儿子结点
TreeNode getRightChildNode(TreeNode node);
//判断结点node是否为NULL
int isNullNode(TreeNode node);
Solution: 这里要充分利用完全二叉树的性质。
根据左右子树的高度，可以判断出最后一层最右叶节点的位置，就可以进行二分。
复杂度O(lgn^2)。
*/
// 树的高度，沿着左孩子
int getHeight(TreeNode node)
{
int height = 0;
while (!isNullNode(node)) {
height++;
node = getLeftChildNode(node);
}
return height;
}
// 高度为height的满二叉树节点个数
int count_perfect_binary_tree_nodes(int height)
{
return (int)pow(2, height) - 1;
}
int count_complete_binary_tree_nodes(TreeNode root)
{
int count = 0;
while (!isNullNode(root))
{
int left = getHeight(getLeftChildNode(root));
int right = getHeight(getRightChildNode(root));
if (left == right)
{
count += count_perfect_binary_tree_nodes(left) + 1;
root = getRightChildNode(root);
}
else
{
count += count_perfect_binary_tree_nodes(right) + 1;
root = getLeftChildNode(root);
}
}
return count;
}
//使用getLeftChildNode(TreeNode)获得左儿子结点 //使用getRightChildNode(TreeNode)获得右儿子结点 //使用isNullNode(TreeNode)判断结点是否为空 int count_complete_binary_tree_nodes(TreeNode root) { if(isNullNode(root)) return 0; TreeNode left = getLeftChildNode(root); int left_height = 0; while(!isNullNode(left)){ left = getLeftChildNode(left); left_height += 1; } int right_height = 0; TreeNode right = getRightChildNode(root); while(!isNullNode(right)){ right = getRightChildNode(right); right_height += 1; } if(left_height == right_height){ return (2 << left_height) -1; } return count_complete_binary_tree_nodes(getLeftChildNode(root)) + count_complete_binary_tree_nodes(getRightChildNode(root)) + 1; }
Read full article from [itint5]完全二叉树节点个数的统计 - 阿牧遥 - 博客园
这题是利用完全二叉树的性质计算节点数目。那么是通过比较左右子树的最左结点的高度来看那边是满的，然后递归计算。
给定一棵完全二叉树的根结点，统计该树的结点总数。
树结点类型名为TreeNode，您没必要知道该类型的定义，请使用下面的方法得到某个结点的左，右儿子结点，以及判断某结点是否为NULL。
https://github.com/AnnieKim/ITint5/blob/master/004_%E7%BB%9F%E8%AE%A1%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%BB%93%E7%82%B9%E6%95%B0.cpp
//获得结点node的左儿子结点
TreeNode getLeftChildNode(TreeNode node);
//获得结点node的右儿子结点
TreeNode getRightChildNode(TreeNode node);
//判断结点node是否为NULL
int isNullNode(TreeNode node);
Solution: 这里要充分利用完全二叉树的性质。
根据左右子树的高度，可以判断出最后一层最右叶节点的位置，就可以进行二分。
复杂度O(lgn^2)。
*/
// 树的高度，沿着左孩子
int getHeight(TreeNode node)
{
int height = 0;
while (!isNullNode(node)) {
height++;
node = getLeftChildNode(node);
}
return height;
}
// 高度为height的满二叉树节点个数
int count_perfect_binary_tree_nodes(int height)
{
return (int)pow(2, height) - 1;
}
int count_complete_binary_tree_nodes(TreeNode root)
{
int count = 0;
while (!isNullNode(root))
{
int left = getHeight(getLeftChildNode(root));
int right = getHeight(getRightChildNode(root));
if (left == right)
{
count += count_perfect_binary_tree_nodes(left) + 1;
root = getRightChildNode(root);
}
else
{
count += count_perfect_binary_tree_nodes(right) + 1;
root = getLeftChildNode(root);
}
}
return count;
}
http://lixinzhang.github.io/itint5-mian-shi-ti-zong-jie.html
给定一棵完全二叉树（查看定义）的根结点，统计该树的结点总数。
树结点类型名为TreeNode，您没必要知道该类型的定义，请使用下面的方法得到某个结点的左，右儿子结点，以及判断某结点是否为NULL。
分析
O(n)的方法肯定是不行的，因为没有借助完全二叉树的特性。 于是，考虑计算最左边树高度，与最右边树高度，如果两个值相等，那么这棵子树的为一颗满二叉树，其节点个数自然就是已知的了，为2height−1 .
递归去做。传说中hulu的面试题。
//使用getLeftChildNode(TreeNode)获得左儿子结点 //使用getRightChildNode(TreeNode)获得右儿子结点 //使用isNullNode(TreeNode)判断结点是否为空 int count_complete_binary_tree_nodes(TreeNode root) { if(isNullNode(root)) return 0; TreeNode left = getLeftChildNode(root); int left_height = 0; while(!isNullNode(left)){ left = getLeftChildNode(left); left_height += 1; } int right_height = 0; TreeNode right = getRightChildNode(root); while(!isNullNode(right)){ right = getRightChildNode(right); right_height += 1; } if(left_height == right_height){ return (2 << left_height) -1; } return count_complete_binary_tree_nodes(getLeftChildNode(root)) + count_complete_binary_tree_nodes(getRightChildNode(root)) + 1; }
Read full article from [itint5]完全二叉树节点个数的统计 - 阿牧遥 - 博客园
