LeetCode222. 完全二叉树的节点个数
题目链接：LeetCode222
常规思路，遍历整棵树，时间复杂度O(N)，但是有一种时间复杂度小于O(N)的做法 首先遍历头结点右子树的最左边界，如果最左边界不为空，说明头结点的左子树是满二叉树，利用满二叉树的性质，结点个数就为2^h^-1，再加上头结点，所以结果就是2^h^，这个时间复杂度是O(logN)的，然后再递归遍历右子树求出有多少结点即可 如果最左边界为空，说明头结点的右子树是一棵高度为h-1的满二叉树，那么右子树加上头结点的总结点个数就为2^h-1^，然后再递归遍历头节点的左子树即可
class Solution {
int h;
public int countNodes(TreeNode root) {
h = mostLeftLevel(root,1);
if(root == null)
return 0;
return bs(root,1);
}
public int bs(TreeNode node,int level) {
if(level == h)
return 1;
if(mostLeftLevel(node.right,level + 1) == h)
return (1 << (h - level)) + bs(node.right,level + 1);
return (1 << (h - level - 1)) + bs(node.left,level + 1);
}
public int mostLeftLevel(TreeNode node,int level) {
while(node != null) {
level++;
node = node.left;
}
return level - 1;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-08-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录