Once I realized at least one of the subtrees is perfect binary tree...


  • 0
    B

    As I mentioned, the key to this problem is at least one of the subtrees is a perfect tree, full complete tree, or both of them are.
    Thus, by using O(lgn) time, which is for finding the "height", I can reduce the problem to n/2, or at most 2n/3? (I'm not so sure) So the total time complexity is O(lgn * lgn) !

    public class Solution {
        public int countNodes(TreeNode root) {
            if (root == null) return 0;
            int left = findHeight(root.left);
            int right = findHeight(root.right);
                return left == right ? (1 << left) + countNodes(root.right) : (1 << right) + countNodes(root.left);
        }
        private int findHeight(TreeNode root) {
            int height = 0;
            while (root != null) {
                root = root.left;
                height++;
            }
            return height;
        }
    }
    

    My first time to explain my code, hope it helps and open to any comments. ^_^


Log in to reply
 

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