222. Count Complete Tree Nodes

222. Count Complete Tree Nodes

Question

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

Thinking:

• Method 1：bfs TLE

/**
 * 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) {
        int result = 0;
        if(root == null) return result;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode temp = queue.poll();
            result++;
            if(temp.left != null) queue.add(temp.left);
            if(temp.right != null) queue.add(temp.right);
        }
        return result;
    }
}

• Method 2: DFS TLE

/**
 * 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;
        else
            return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

• Method 3: 利用完全二叉树的性质 AC

/**
 * 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 = leftHeight(root);
        int right = rightHeight(root);
        if(left == right) return (1 << left) - 1;
        else
            return 1 + countNodes(root.left) + countNodes(root.right);
    }
    private int leftHeight(TreeNode root){
        if(root == null) return 0;
        else
            return leftHeight(root.left) + 1;
    }
    private int rightHeight(TreeNode root){
        if(root == null) return 0;
        else
            return rightHeight(root.right) + 1;
    }
}

二刷

1. DFS

   /**
    * Definition for a binary tree node.
    * public class TreeNode {
    *     int val;
    *     TreeNode left;
    *     TreeNode right;
    *     TreeNode(int x) { val = x; }
    * }
    */
   class Solution {
    int count = 0;
    public int countNodes(TreeNode root) {
        dfs(root);
        return this.count;
    }
    private void dfs(TreeNode node){
        if(node == null) return;
        count ++;
        if(node.left != null) dfs(node.left);
        if(node.right != null) dfs(node.right);
    }
   }
   

2. 仍是使用DFS，不使用额外的成员变量。

   /**
    * 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;
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
   }