LeetCode 222: 完全二叉树的节点个数(java)_完全二叉树叶子节点个数公式java

给出一个完全二叉树，求出该树的节点个数。

说明：

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例:

输入: 
    1
   / \
  2   3
 / \  /
4  5 6

输出: 6

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
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<<root.left);
    }else{
        return countNodes(root.left)+(1<<root.right)
    }
    
    private int countLevel(TreeNode root){
        int level = 0;
        while(root != null){
            root = root.left;
            k++;
        }
        return level;   
 
}

方法一：线性时间
算法：

最简单的解决方法就是用递归一个一个的计算节点。

 
class Solution {
  public int countNodes(TreeNode root) {
    return root != null ? 1 + countNodes(root.right) + countNodes(root.left) : 0;
  }
}

复杂度分析

时间复杂度：\mathcal{O}(N)O(N)。
空间复杂度：\mathcal{O}(d) = \mathcal{O}(\log N)O(d)=O(logN)，其中 dd 指的是树的的高度，运行过程中堆栈所使用的空间。
方法二：二分搜索
方法一没有利用完全二叉树的特性。完全二叉树中，除了最后一层外，其余每层节点都是满的，并且最后一层的节点全部靠向左边。

这说明如果第 k 层不是最后一层，则在第 k 层中将有 2^k 个节点。由于最有一层可能没有完全填充，则节点数在 1 到 2^d 之间，其中 d 指的是树的高度。

我们可以直接计算除了最后一层以外的所有结点个数：

 

现在有两个问题：

最后一层我们需要检查多少个节点？
一次检查的最佳的时间性能是什么？
让我们从第一个问题开始思考。最后一层的叶子节点全部靠向左边，我们可以用二分搜索只检查叶子代替检查全部叶子。

 

让我们思考第二个问题，最后一层的叶子节点索引在 0 到 $2^d - 1$ 之间。如何检查第 idx 节点是否存在？让我们来用二分搜索来构造从根节点到 idx 的移动序列。如，idx = 4。idx 位于 0,1,2,3,4,5,6,7 的后半部分，因此第一步是向右移动；然后 idx 位于 4,5,6,7 的前半部分，因此第二部是向左移动；idx 位于 4,5 的前半部分，因此下一步是向左移动。一次检查的时间复杂度为 {O}(d)O(d)。

我们需要{O}(d)O(d) 次检查，一次检查需要{O}(d)O(d)，所以总的时间复杂度为{O}(d^2)O(d`2 )。

算法：

class Solution:
    def compute_depth(self, node: TreeNode) -> int:
        """
        Return tree depth in O(d) time.
        """
        d = 0
        while node.left:
            node = node.left
            d += 1
        return d
 
    def exists(self, idx: int, d: int, node: TreeNode) -> bool:
        """
        Last level nodes are enumerated from 0 to 2**d - 1 (left -> right).
        Return True if last level node idx exists. 
        Binary search with O(d) complexity.
        """
        left, right = 0, 2**d - 1
        for _ in range(d):
            pivot = left + (right - left) // 2
            if idx <= pivot:
                node = node.left
                right = pivot
            else:
                node = node.right
                left = pivot + 1
        return node is not None
        
    def countNodes(self, root: TreeNode) -> int:
        # if the tree is empty
        if not root:
            return 0
        
        d = self.compute_depth(root)
        # if the tree contains 1 node
        if d == 0:
            return 1
        
        # Last level nodes are enumerated from 0 to 2**d - 1 (left -> right).
        # Perform binary search to check how many nodes exist.
        left, right = 1, 2**d - 1
        while left <= right:
            pivot = left + (right - left) // 2
            if self.exists(pivot, d, root):
                left = pivot + 1
            else:
                right = pivot - 1
        
        # The tree contains 2**d - 1 nodes on the first (d - 1) levels
        # and left nodes on the last level.
        return (2**d - 1) + left

 

 

作者：LeetCode
链接：https://leetcode-cn.com/problems/count-complete-tree-nodes/solution/wan-quan-er-cha-shu-de-jie-dian-ge-shu-by-leetcode/
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。