找回密码
 立即注册
首页 业界区 科技 算法day13——二叉树(3)

算法day13——二叉树(3)

章娅萝 3 天前
目录


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

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

  方法一:用普适的递归方法来做,这样会遍历到每一个节点。没有利用完全二叉树的性质。
  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
您需要登录后才可以回帖 登录 | 立即注册