美文网首页
222. 完全二叉树的节点个数

222. 完全二叉树的节点个数

作者: 编程小王子AAA | 来源:发表于2020-08-17 09:30 被阅读0次

    222. 完全二叉树的节点个数

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

    说明:

    完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 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 {
      // Return tree depth in O(d) time.
      public int computeDepth(TreeNode node) {
        int d = 0;
        while (node.left != null) {
          node = node.left;
          ++d;
        }
        return d;
      }
    
      // 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.
      public boolean exists(int idx, int d, TreeNode node) {
        int left = 0, right = (int)Math.pow(2, d) - 1;
        int pivot;
        for(int i = 0; i < d; ++i) {
          pivot = left + (right - left) / 2;
          if (idx <= pivot) {
            node = node.left;
            right = pivot;
          }
          else {
            node = node.right;
            left = pivot + 1;
          }
        }
        return node != null;
      }
    
      public int countNodes(TreeNode root) {
        // if the tree is empty
        if (root == null) return 0;
    
        int d = computeDepth(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.
        int left = 1, right = (int)Math.pow(2, d) - 1;
        int pivot;
        while (left <= right) {
          pivot = left + (right - left) / 2;
          if (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 (int)Math.pow(2, d) - 1 + left;
      }
    }
    

    相关文章

      网友评论

          本文标题:222. 完全二叉树的节点个数

          本文链接:https://www.haomeiwen.com/subject/lazpdktx.html