Maximum Depth of Binary Tree--LeetCode

冷不防 2022-08-07 11:55 28阅读 0赞

题目：

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. int MaxDepth(BinTree* root)
  2. {
  3.     if(root == NULL)
  4.         return 0;
  5.     else
  6.         return max(MaxDepth(root->left),MaxDepth(root->right))+1;
  7. }

非递归解法一般采用层序遍历(相当于图的BFS），因为如果使用其他遍历方式也需要同样的复杂度O(n). 层序遍历理解上直观一些，维护到最后的level便是树的深度。代码如下： 

  1. int MaxDepth(BinTree* root)
  2. {
  3.     if(root == NULL)
  4.         return 0;
  5.     deque<BinTree*> de;
  6.     int num;
  7.     int curnum=0;
  8.     int level=0;
  9.     BinTree* node;
  10.     de.push_back(root);
  11.     num =1;
  12.     while(!de.empty())
  13.     {
  14.         node = de.front();
  15.         de.pop_front();
  16.         num--;
  17.         if(node->left != NULL)
  18.         {
  19.             de.push_back(node->left);
  20.             curnum++;
  21.         }
  22.         if(node->right !=NULL)
  23.         {
  24.             de.push_back(node->right);
  25.             curnum++;
  26.         }
  27.         if(num ==0)
  28.         {
  29.             num =curnum;
  30.             curnum =0;
  31.             level++;
  32.         }
  33.     }
  34.     return level;
  35. }

发表评论

表情：
评论列表 （有 0 条评论，28人围观）

还没有评论，来说两句吧...

相关阅读