算法day13——二叉树（3）

目录

• 完全二叉树的节点个数
  
• 平衡二叉树110
  
• 二叉树的所有路径257
  
• 左叶子之和404
  

一、完全二叉树的节点个数

 https://leetcode.cn/problems/count-complete-tree-nodes/description/?envType=problem-list-v2&envId=8At1GmaZ

 　方法一：用普适的递归方法来做，这样会遍历到每一个节点。没有利用完全二叉树的性质。

1. class Solution {
2.     public int countNodes(TreeNode root) {
3.         if(root == null){
4.             return 0;
5.         }
6.         return countNodes(root.left) + countNodes(root.right) + 1;
7.     }
8. }
9. //时间复杂度：O（n）

复制代码

　　方法二：充分利用了“完全二叉树”的结构，避免了重复计算完整子树的节点个数，大大减少了递归次数，因此时间复杂度从 O(n) 降低到了 O((log n)^2)，在大数据量时性能优势明显。

• 完全二叉树的特点是：左子树深度等于右子树深度 ⇒ 整个左子树是满二叉树，节点数是 2^depth - 1。
  
• 利用这一性质，可以直接跳过对整棵子树的递归计算，用位运算直接得出节点数。
  

[code]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