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

The editor of this article introduces in detail "how to achieve the maximum depth of the binary tree by C++". The content is detailed, the steps are clear, and the details are handled properly. I hope that this article "how to achieve the maximum depth of the binary tree by C++" can help you solve your doubts. Let's follow the editor's ideas to slowly deepen, together to learn new knowledge.

Maximum depth of binary tree

Example:

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

three

/

9 20

/

15 7

Return its depth = 3.

The problem of finding the maximum depth of a binary tree uses a depth-first search Depth First Search. The perfect application of recursion is the same as finding the minimum depth of a binary tree. See the code below:

C++ solution one:

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

Java solution 1:

Public class Solution {public int maxDepth (TreeNode root) {return root = = null? 0: (1 + Math.max (maxDepth (root.left), maxDepth (root.right));}}

We can also use the sequence to traverse the binary tree, and then count the total number of layers, that is, the maximum depth of the binary tree. Note that the for loop in the while loop has a trick. Be sure to put q.size () in the initialization, but not in the condition for judging the stop. Because the size of Q changes at any time, there will be an error in the stop condition. See the code below:

C++ solution 2:

Class Solution {public: int maxDepth (TreeNode* root) {if (! root) return 0; int res = 0; queue Q {{root}}; while (! q.empty ()) {+ + res; for (int I = q.size (); I > 0;-I) {TreeNode* t = q.front (); q.pop () If (t-> left) q.push (t-> left); if (t-> right) q.push (t-> right);} return res;}}

Java solution II:

Public class Solution {public int maxDepth (TreeNode root) {if (root = = null) return 0; int res = 0; Queue Q = new LinkedList (); q.offer (root); while (! q.isEmpty ()) {+ + res; for (int I = q.size (); I > 0;-I) {TreeNode t = q.poll () If (t.left! = null) q.offer (t.left); if (t.right! = null) q.offer (t.right);}} return res }} after reading this, the article "how to achieve the maximum depth of the binary tree by C++" has been introduced. If you want to master the knowledge points of this article, you still need to practice and use it before you can understand it. If you want to know more about related articles, welcome to follow 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.