222. Count Complete Tree Nodes.md

222. Count Complete Tree Nodes

---

leetcode Daily Challenge on June 23, 2020.

leetcode-cn Daily Challenge on November 24, 2020.

leetcode Daily Challenge on November 15, 2022.

---

Given a complete binary tree, count the number of nodes.

Note:

Definition of a complete binary tree from Wikipedia:

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example:

Input:
    1
   / \
  2   3
 / \  /
4  5 6

Output: 6

---

Solution

• mine
  • Java

    • Runtime: 0 ms, faster than 100.00%, Memory Usage: 41.9 MB, less than 71.91% of Java online submissions

      // O(N)time O(D)space
      // D is tree depth
      public int countNodes(TreeNode root) {
          return root == null ? 0 : 1 + countNodes(root.left) + countNodes(root.right);
      }
      

    • Runtime: 0 ms, faster than 100.00%, Memory Usage: 41.6 MB, less than 96.56% of Java online submissions

      // O(D^2)time O(1)space
      // D is tree depth
      public int countNodes(TreeNode root) {
          if (root == null) {
              return 0;
          }
          int depth = getDepth(root);
          if (depth == 0) {
              return 1;
          }
          int count = (int) Math.pow(2, depth) - 1;
          //1 - 2^depth
          int s = 1, e = count + 1;
          while (s <= e) {
              int mid = (e + s) / 2;
              if (exists(mid, depth - 1, root)) {
                  s = mid + 1;
              } else {
                  e = mid - 1;
              }
          }
          return count + s - 1;
      }
      
      int getDepth(TreeNode node) {
          int depth = 0;
          while (node.left != null) {
              depth++;
              node = node.left;
          }
          return depth;
      }
      
      boolean exists(int index, int d, TreeNode node) {
          while (d >= 0) {
              int size = (int) Math.pow(2, d);
              if (index > size) {
                  node = node.right;
                  index -= size;
              } else {
                  node = node.left;
              }
              d--;
          }
          return node != null;
      }
      

    • DFS

      private int size = 0;
      public int countNodes(TreeNode root) {
          size = 0;
          dfs(root);
          return size;
      }
      
      private void dfs(TreeNode root){
          if(root == null){
              return;
          }
          size++;
          dfs(root.left);
          dfs(root.right);
      }
      

---