Shulou(Shulou.com)05/31 Report--

Today, the editor will share with you the relevant knowledge points about how C++ can achieve the minimum depth of the binary tree. The content is detailed and the logic is clear. I believe most people still know too much about this knowledge, so share this article for your reference. I hope you can get something after reading this article, let's take a look at it.

Minimum depth of binary tree

Example:

Given binary tree [3,9,20,null,null,15,7]

three

/

9 20

/

15 7

Return its minimum depth = 2.

The minimum depth problem of the classic binary tree problem is the number of nodes in the shortest path, or using depth-first search DFS to complete, omnipotent recursion. First, it is null, and if the current node does not exist, 0 is returned directly. Then if the left child node does not exist, then call the recursive function on the right child node and add 1 to return. Conversely, if the right child node does not exist, then call the recursive function on the left child node and add 1 to return. If both left and right child nodes exist, the recursive function is called on the left and right child nodes respectively, and the smaller value of the two is returned by adding 1. See the code as follows:

Solution 1:

Class Solution {public: int minDepth (TreeNode* root) {if (! root) return 0; if (! root- > left) return 1 + minDepth (root- > right); if (! root- > right) return 1 + minDepth (root- > left); return 1 + min (minDepth (root- > left), minDepth (root- > right);}}

We can also do it iteratively, traversing the sequence and recording the number of layers traversed. Once traversing to the first leaf node, the current number of layers is returned, that is, the minimum depth of the binary tree. See the code below:

Solution 2:

Class Solution {public: int minDepth (TreeNode* root) {if (! root) return 0; int res = 0; queue Q {{root}}; while (! q.empty ()) {+ + res; for (int I = q.size (); I > 0;-I) {auto t = q.front (); q.pop () If (! t-> left & &! t-> right) return res; if (t-> left) q.push (t-> left); if (t-> right) q.push (t-> right);}} return-1;}} These are all the contents of the article "how to achieve the minimum depth of the binary tree on C++". Thank you for reading! I believe you will gain a lot after reading this article. The editor will update different knowledge for you every day. If you want to learn more knowledge, please pay attention to the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.