当前位置: 首页 > 文档资料 > LeetCode 题解 >

Tree - Depth of Binary Tree

优质
小牛编辑
131浏览
2023-12-01

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.

这题要求我们求出一个二叉树最大深度,也就是从根节点到最远的叶子节点的距离。

对于这题,我们只需要递归遍历二叉树,达到一个叶子节点的时候,记录深度,我们就能得到最深的深度了。

代码如下:

  1. class Solution {
  2. public:
  3. int num;
  4. int maxDepth(TreeNode *root) {
  5. if(!root) {
  6. return 0;
  7. }
  8. //首先初始化num为最小值
  9. num = numeric_limits<int>::min();
  10. travel(root, 1);
  11. return num;
  12. }
  13. void travel(TreeNode* node, int level) {
  14. //如果没有左子树以及右子树了,就到了叶子节点
  15. if(!node->left && !node->right) {
  16. num = max(num, level);
  17. return;
  18. }
  19. if(node->left) {
  20. travel(node->left, level + 1);
  21. }
  22. if(node->right) {
  23. travel(node->right, level + 1);
  24. }
  25. }
  26. };

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

这题跟上题几乎一样,区别在于需要求出根节点到最近的叶子节点的深度,我们仍然使用遍历的方式。

代码如下:

  1. class Solution {
  2. public:
  3. int n;
  4. int minDepth(TreeNode *root) {
  5. if(!root) {
  6. return 0;
  7. }
  8. //初始化成最大值
  9. n = numeric_limits<int>::max();
  10. int d = 1;
  11. depth(root, d);
  12. return n;
  13. }
  14. void depth(TreeNode* node, int& d) {
  15. //叶子节点,比较
  16. if(!node->left && !node->right) {
  17. n = min(n, d);
  18. return;
  19. }
  20. if(node->left) {
  21. d++;
  22. depth(node->left, d);
  23. d--;
  24. }
  25. if(node->right) {
  26. d++;
  27. depth(node->right, d);
  28. d--;
  29. }
  30. }
  31. };