Hello, everyone! Today we will learn how to solve algorithm problems using C#. The topic for this session is to find the number of leaf nodes in a binary tree. By solving this problem, you can enhance your understanding of data structures and recursive calls.<\/p>\n
The problem is as follows: Given a binary tree, write a function to count the number of leaf nodes (nodes with no children).<\/p>\n
\n 1\n \/ \\\n 2 3\n \/ \\\n 4 5\n <\/pre>\n
A binary tree is a tree data structure in which each node can have at most two children. A binary tree has the following characteristics:<\/p>\n
To count the number of leaf nodes, let’s consider using a recursive function. The basic approach is as follows:<\/p>\n
Now, let’s implement the code in C# according to the approach described above.<\/p>\n
\nusing System;\n\nclass TreeNode\n{\n public int Val;\n public TreeNode Left;\n public TreeNode Right;\n\n public TreeNode(int val)\n {\n Val = val;\n Left = null;\n Right = null;\n }\n}\n\nclass Program\n{\n public static int CountLeafNodes(TreeNode root)\n {\n \/\/ 1. If the current node is null\n if (root == null)\n return 0;\n\n \/\/ 2. If the current node is a leaf node\n if (root.Left == null && root.Right == null)\n return 1;\n\n \/\/ 3. Count leaf nodes in the left and right subtrees\n return CountLeafNodes(root.Left) + CountLeafNodes(root.Right);\n }\n\n static void Main(string[] args)\n {\n \/\/ Create the tree\n TreeNode root = new TreeNode(1);\n root.Left = new TreeNode(2);\n root.Right = new TreeNode(3);\n root.Left.Left = new TreeNode(4);\n root.Left.Right = new TreeNode(5);\n\n \/\/ Print the count of leaf nodes\n int leafCount = CountLeafNodes(root);\n Console.WriteLine($\"Number of leaf nodes: {leafCount}\");\n }\n}\n<\/pre>\n5. Code Explanation<\/h2>\n
The provided TreeNode<\/code> class defines a node in the binary tree. Each node has a value (Val) and left (Left) and right (Right) child nodes. The CountLeafNodes<\/code> function recursively calculates the number of leaf nodes for the given node.<\/p>\n\n- In the first conditional statement, if the current node is null, it returns 0 to terminate.<\/li>\n
- In the second conditional statement, if the current node is a leaf node, it returns 1.<\/li>\n
- Finally, it visits the left and right subtrees, sums up the results, and returns the total.<\/li>\n<\/ul>\n
6. Time Complexity Analysis<\/h2>\n
The time complexity of this algorithm is O(N). Here, N represents the number of nodes in the tree. Since each node is visited only once, it has a linear time complexity.<\/p>\n
7. Additional Considerations<\/h2>\n