Clean C++ code (recursive and iterative)


  • 0
    P

    I know there is already a high rated answer here https://discuss.leetcode.com/topic/15533/concise-java-solutions-o-log-n-2. Just share concise C++ codes based on the same idea: one of left or right subtree is PERFECT tree (whose node count is a math), the other can be solved by a "recursive" call. Below are a pure recursive solution and a pure iterative solution.

    1. Recursive solution

    class Solution {
    private:
        int getHeight(TreeNode * root) {
            return root == NULL ? 0 : 1 + getHeight(root->left);
        }
        
        int calPerfectTree(int h) {
            return (1<<h) - 1;
        }
        
        int count(TreeNode * root, int h) {
            if (!root)  return 0;
            int rh = getHeight(root->right);
            return (rh == h - 1) ? 1 + calPerfectTree(h-1) + count(root->right, h-1) : 1 + calPerfectTree(h-2) + count(root->left, h-1);
        }
        
    public:
        int countNodes(TreeNode* root) {
            return count(root, getHeight(root));
        }
    };
    

    2. Iterative solution

    class Solution {
    private:
        int getHeight(TreeNode * root) {
            int h = 0;
            for (; root != NULL; h++, root = root->left);
            return h;
        }
        
        int calPerfectTree(int h) {
            return (1<<h) - 1;
        }
        
    public:
        int countNodes(TreeNode* root) {
            int res = 0, h = getHeight(root), rh;
            while (root) {
                rh = getHeight(root->right);
                res += 1 + ((rh == h - 1) ? calPerfectTree(h-1) : calPerfectTree(h-2));
                root = (rh == h - 1) ? root->right : root->left;
                --h;
            }
            return res;
        }
    };
    

Log in to reply
 

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