Divide and Conquer (binary search) Java solution (beats 80%) with comments


  • 0
    B

    So the idea is the following:

    First check if we have a complete filled tree, if yes we know how much nodes we have: 2^h - 1 where h is the height of the tree.

    Otherwise we know that the number of nodes = 2^(h-1) - 1 + lastLevel, where lastLevel is the number of leafes on the last level.

    To get the number of nodes on the last level, we do a D&C logic: first check if there is a middle node on the last level: Basically get the height of the most right node from the left of the current node. If the mh height of that node equals to h we have middle node otherwise not.

    • if we have a middle node on the last level, we need to count on the right side + we know that on the left we had (1 << (h-2)).
    • if there is no middle, we know that we have less then (1 << (h-2)) bottom nodes, and we continue our search on the left side.
    public class Solution {
        public int countNodes(TreeNode root) {
            if(root == null) return 0;
            
            // get the height of the most left node
            TreeNode current = root;
            int lh = 1;
            while((current = current.left) != null) lh++;
    
            // get the height of the most right node
            current = root;
            int rh = 1;
            while((current = current.right) != null) rh++;
            
            // if the left and right heights are the same, we have the last level filled,
            // so: N = 2^h - 1
            if(lh == rh) return (1 << lh) - 1;
            
            // otherwise N = 2^(h-1) - 1 + <number of leaves>
            return (1 << rh) - 1 + lastLevel(root, lh);
        }
        
        private int lastLevel(TreeNode root, int h) {
            // if the height is 1, we have only 1 node
            if(h == 1) {
                return 1;
            } else if(h == 2) {
                // if the height is 2, we check left and right to count the last level nodes: 0, 1 or 2
                return root.left == null ? 0 : (root.right != null ? 2 : 1);
            }
            
            // divide and conquer, first we find the 'middle' node on the last level
            TreeNode mid = root.left;
            int mh = 2;
            while((mid = mid.right) != null) mh++;
            
            if(mh == h) {
                // we do have a middle node, so we know that the number of nodes on the last level=
                // the number bottom nodes on the left side which is: (1 << (h-2))
                // + the number of bottom nodes on the right side
                return (1 << (h-2)) + lastLevel(root.right, h-1);
            } else {
                // if there is no middle node, we know that we must count them on the left side
                return lastLevel(root.left, h-1);
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.