Leetcode 完全二叉树的节点个数
不讲武德的解法
java 实现
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
根据完全二叉树和满二叉树的性质做
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = getDepth(root.left);
int rightDepth = getDepth(root.right);
if (leftDepth == rightDepth) {
// 左子树是满二叉树，节点数为 2^leftDepth - 1，加上根节点和右子树
return (1 << leftDepth) + countNodes(root.right);
} else {
// 右子树是满二叉树，节点数为 2^rightDepth - 1，加上根节点和左子树
return (1 << rightDepth) + countNodes(root.left);
}
}
private int getDepth(TreeNode node) {
int depth = 0;
while (node != null) {
depth++;
node = node.left; // 完全二叉树的最左路径
}
return depth;
}
}
原文地址：https://blog.csdn.net/coldasice342/article/details/143950488
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！