力扣 LeetCode 222. 完全二叉树的节点个数(Day7:二叉树)
解题思路:
解法一:普通二叉树解法
使用后序遍历
有一行的精简版代码但不利于理解采用的哪一种遍历方式
解法二:利用上完全二叉树的特点
一个指针left,一个指针right
left一直向左遍历,right一直向右遍历,如果深度相同,那么就是满二叉树,就可以用公式2的n次方-1来计算节点个数
class Solution {
public int countNodes(TreeNode root) {
if (root == null) return 0;
TreeNode left = root.left;
TreeNode right = root.right;
int leftDepth = 0, rightDepth = 0;
while (left != null) {
left = left.left;
leftDepth++;
}
while (right != null) {
right = right.right;
rightDepth++;
}
if (leftDepth == rightDepth)return (2 << leftDepth) - 1;
int lDepth = countNodes(root.left);
int rDepth = countNodes(root.right);
int res = 1 + lDepth + rDepth;
return res;
}
}
原文地址:https://blog.csdn.net/qq_61504864/article/details/143885712
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!