222. Count Complete Tree Nodes

Description

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.

Constraints

Approach

Examples

Input:

[1, 2, 3, 4, 5, 6]

Output:

Solutions

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) {
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * Time complexity : O(N)
 * Space complexity : O(d)=O(logN) to keep the recursion stack, 
 *    where d is a tree depth.
 */

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

/**
 * Time complexity : 
 * Space complexity : 
 */
 
 class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        
        int left = getLeftHeight(root) + 1;
        int right = getRightHeight(root) + 1;
        
        if(left == right) {
            return (2 << (left-1))-1;
        }
        
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
    
    private int getLeftHeight(TreeNode node) {
        if(node == null) return 0;
        
        int height = 0;
        while(node.left != null) {
            height++;
            node = node.left;
        }
        return height;
    }
    
    private int getRightHeight(TreeNode node) {
        if(node == null) return 0;
        
        int height = 0;
        while(node.right != null) {
            height++;
            node = node.right;
        }
        return height;
    }
}

Follow up

Previous221. Maximal Square Next223. Rectangle Area

Last updated 5 years ago

Was this helpful?