Java iterative solution beats 100% O(log(n)^2) with detailed explanation


  • 2

    Unlike many of the recursive solutions my solution is to iteratively count the the number of nodes in the partially full layer (last layer if exsiting). It first compute the depth of the right most leave of the whole tree which is the depth of a complete tree. Then it compute the depth of right most leave of the left subtree. If they don't equal to each other, the left subtree is complete tree, we add the number of nodes of the last layer of left subtree and move to right subtree. Otherwise we know the right is complete tree and move to the leftsubtree. Repeat the process till the node is null.

    private static int rightMostDepth(TreeNode root) {  //the depth from root to the right most leave
            int depth = 0;
            while (root != null) {
                depth++;
                root = root.right;
            }
            return depth;
        }
        public static int countNodes(TreeNode root) {
            int depth = rightMostDepth(root);   //depth of the last full level
            int result = (1 << depth) - 1;  //num of nodes from root to the last full level
            TreeNode cur = root;
            int rootdepth = 1;
            while (cur != null) {
                int leftdepth = rightMostDepth(cur.left);
                if (leftdepth + rootdepth == depth) cur = cur.left; //the partially full level ends within the left subtree
                else {  //ends in the right subtree
                    result += (1 << leftdepth - 1); //add the number of nodes in the partially full level within the left subtree
                    cur = cur.right;    //continue to search for the end point of partially full level
                }
                rootdepth++;
            }
            return result;
        }
    

  • 0

Log in to reply
 

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