算法day13——二叉树（3）
目录[*]完全二叉树的节点个数
[*]平衡二叉树110
[*]二叉树的所有路径257
[*]左叶子之和404
一、完全二叉树的节点个数
https://leetcode.cn/problems/count-complete-tree-nodes/description/?envType=problem-list-v2&envId=8At1GmaZ
方法一：用普适的递归方法来做，这样会遍历到每一个节点。没有利用完全二叉树的性质。
class Solution {
public int countNodes(TreeNode root) {
if(root == null){
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
//时间复杂度：O（n） 方法二：充分利用了“完全二叉树”的结构，避免了重复计算完整子树的节点个数，大大减少了递归次数，因此时间复杂度从 O(n) 降低到了 O((log n)^2)，在大数据量时性能优势明显。
[*]完全二叉树的特点是：左子树深度等于右子树深度 ⇒ 整个左子树是满二叉树，节点数是 2^depth - 1。
[*]利用这一性质，可以直接跳过对整棵子树的递归计算，用位运算直接得出节点数。
class Solution { public int countNodes(TreeNode root) { if(root == null){ return 0; } int left = countLevel(root.left); int right = countLevel(root.right); if(left == right){ return countNodes(root.right) + (1
页:
[1]