C# accepted recursive


  • 0
    R

    The count of nodes in complete binary tree is formed by two parts:

    1. All nodes except the last layer: 2 ^ (treeDepth - 1) - 1;

    2. nodes on the last layer:

    for this part, we use a recusive divide and conquer method, CountLastLayerNodes, as shown below:

        public int CountNodes(TreeNode root)
        {
            if (root == null)
            {
                return 0;
            }
            if (root.left == null && root.right == null)
            {
                return 1;
            }
    
            int leftDepth = GetLeftDepth(root);
            int nodeCountWithoutLastLayer = (int)Math.Pow(2, leftDepth) - 1;
            int nodeCountOnLastLayer = CountLastLayerNodes(root);
            return (nodeCountWithoutLastLayer + nodeCountOnLastLayer);
        }
    
        public static int CountLastLayerNodes(TreeNode root)
        {
            int count = 0;
            if (root == null)
            {
                return count;
            }
    
            if (root.left == null && root.right == null)
            {
                return 0;
            }
    
            if (root.left != null && root.right == null)
            {
                return 1;
            }
    
            int leftleftDepth = GetLeftDepth(root.left);
            int leftrightDepth = GetRightDepth(root.left);
            int rightleftDepth = GetLeftDepth(root.right);
            int rightrightDepth = GetRightDepth(root.right);
    
            if (leftleftDepth == rightrightDepth)
            {
                return (int)Math.Pow(2, leftleftDepth + 1);
            }
            else if (leftleftDepth == rightleftDepth)
            {
                return (int)Math.Pow(2, leftleftDepth) + CountLastLayerNodes(root.right);
            }
            else if (leftleftDepth == leftrightDepth)
            {
                return (int)Math.Pow(2, leftleftDepth);
            }
            else
            {
                return CountLastLayerNodes(root.left);
            }
        }
    
        public static int GetLeftDepth(TreeNode node)
        {
            TreeNode temp = node;
            int depth = 0;
            while (temp != null)
            {
                if (temp.left != null)
                {
                    temp = temp.left;
                    depth++;
                }
                else
                {
                    break;
                }
            }
            return depth;
        }
    
        public static int GetRightDepth(TreeNode node)
        {
            TreeNode temp = node;
            int depth = 0;
            while (temp != null)
            {
                if (temp.right != null)
                {
                    temp = temp.right;
                    depth++;
                }
                else
                {
                    break;
                }
            }
            return depth;
        }

  • 1
    R

    Saw others' code, seems this one is easier to understand:

    public int CountNodes(TreeNode root)
    {
        if (root == null)
        {
            return 0;
        }
        
        int leftDepth = GetLeftDepth(root);
        int rightDepth = GetRightDepth(root);
        if (leftDepth == rightDepth)
        {
            return (int)Math.Pow(2, leftDepth + 1) - 1;
        }
        else
        {
            return (1 + CountNodes(root.left) + CountNodes(root.right));
        }
    }

  • 0

    Combine 1st post and 2nd post it should work.

    Finally a answer not using Shift operator. I find shift operators are less human readable, though it's fast and lead TLE....but I think it's OK for interviewing.
    You could combine GetLeftDepth() and GetRightDepth into GetDpeth()


Log in to reply
 

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