C# solution. Only need to count the height of the right sub-tree.


  • 0
    R

    I see some solutions are counting and compare the height of both left and right sub-trees. We actually only need to count the height of the right sub-tree, which can be either height-1 or height-2, then we know which sub-tree is the perfect BST, and which side to go next.

    public int CountNodes(TreeNode root) {
            int depth;
            int cntNodes=0;
    
            if (root == null) return 0;
    
            depth = TreeDepth(root);
            if (depth == 1) return 1;
    
            while (root != null)
            {
                if (TreeDepth(root.right) < depth - 1)
                {
                    root = root.left;
                    cntNodes += 1 << (depth - 1);
                }
                else
                {
                    root = root.right;
                    cntNodes += 1 << (depth - 2);
                }
                depth--;
            }
            return cntNodes;
    }    
    
        public int TreeDepth(TreeNode root)
        {
            int depth = 0;
    
            while (root != null)
            {
                depth++;
                root = root.left;
            }
    
            return depth;
        }

Log in to reply
 

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