c/c++开发分享C++实现LeetCode(104.二叉树的最大深度)

[leetcode] 104. maximum depth of binary tree 二叉树的最大深度given a binary tree, find its maximum depth.the


[leetcode] 104. maximum depth of binary tree 二叉树的最大深度

given a binary tree, find its maximum depth.

the maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

note: a leaf is a node with no children.

example:

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

    3
/
9  20

15   7

return its depth = 3.

求二叉树的最大深度问题用到深度优先搜索 depth first search,递归的完美应用,跟求二叉树的最小深度问题原理相同,参见代码如下:

c++ 解法一:

  class solution {  public:      int maxdepth(treenode* root) {          if (!root) return 0;          return 1 + max(maxdepth(root->left), maxdepth(root->right));      }  };

java 解法一:

  public class solution {      public int maxdepth(treenode root) {          return root == null ? 0 : (1 + math.max(maxdepth(root.left), maxdepth(root.right)));      }  }

我们也可以使用层序遍历二叉树,然后计数总层数,即为二叉树的最大深度,注意 while 循环中的 for 循环的写法有个 trick,一定要将 q.size() 放在初始化里,而不能放在判断停止的条件中,因为q的大小是随时变化的,所以放停止条件中会出错,参见代码如下:

c++ 解法二:

  class solution {  public:      int maxdepth(treenode* root) {          if (!root) return 0;          int res = 0;          queue<treenode*> 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 解法二:

  public class solution {      public int maxdepth(treenode root) {          if (root == null) return 0;          int res = 0;          queue<treenode> 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;      }  }

github 同步地址:

类似题目:

balanced binary tree

minimum depth of binary tree

maximum depth of n-ary tree

参考资料:

到此这篇关于c++实现leetcode(104.二叉树的最大深度)的文章就介绍到这了,更多相关c++实现二叉树的最大深度内容请搜索<猴子技术宅>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<猴子技术宅>!

需要了解更多c/c++开发分享C++实现LeetCode(104.二叉树的最大深度),都可以关注C/C++技术分享栏目—猴子技术宅(www.ssfiction.com)

本文来自网络收集,不代表猴子技术宅立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ssfiction.com/c-cyuyankaifa/675076.html

发表评论

邮箱地址不会被公开。 必填项已用*标注