Tail recursion c++


  • -1
    A

    The idea here is to look only at the most right height.
    Each time we reach a node, we check if the height of the left subtree is equal (-1) the height of the current tree.

    if yes, it means that the only extra leaves can be on its left.

    otherwise, we need to check the right subtree to repeat the same operation and find where the last leaf is. In this case we are garanteed to have 2^heigth /2 leaves since the left subtree will have all its leaves.

    class Solution {
        
        private:
        
        	int getRightDepth(TreeNode* root)
        	{
        		int depth = 0;
        		for (TreeNode* tN = root; tN != nullptr; tN = tN->right, ++depth);
        		return depth;
        	}
        
        	int leavesCount(TreeNode* root, int baseDepth, int maxLeaves, int leavesAcc)
        	{
        		if (root == nullptr)
        			return leavesAcc;
        		int midDepth = getRightDepth(root->left);
        		if (midDepth + 1 == baseDepth)
        			return leavesCount(root->left, midDepth, maxLeaves / 2, leavesAcc);
        		else
        			return  leavesCount(root->right, baseDepth - 1, maxLeaves / 2, leavesAcc + maxLeaves / 2);
        	}
        
        public:
        	int countNodes(TreeNode* root) {
        		int baseDepth = getRightDepth(root);
        		int maxLeaves = pow(2, baseDepth);                  
        		int nb = leavesCount(root, baseDepth, maxLeaves, 0);  
        		return nb + (1 - pow(2, baseDepth)) / (-1);  //sum of the number of leaves with the number of nodes in the complete part
        	}
        };

Log in to reply
 

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