LeetCode1_求二叉树最小深度（树）

佚名 6年前 (2019-05-07) 随笔 311人围观抢沙发百度已收录

题目：

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.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

思路1：利用递归遍历，求最小深度

 1 //递归遍历求最小深度
 2 class Solution {
 3 public:
 4     int run(TreeNode *root) {
 5         if(root ==NULL) 
 6             return 0;
 7         int l = run(root->left);
 8         int r = run(root->right);
 9         if(l==0 || r==0)
10             return l+r+1;
11         return min(l, r) + 1;
12     }
13 };

思路2：利用队列采用层序遍历，一旦找到一个叶节点，它肯定是最短的。

参考链接：

二叉树的层序遍历算法：https://blog.csdn.net/qq_29542611/article/details/79372678

 1 class Solution
 2 {
 3     public:
 4         typedef TreeNode* tree;
 5         int run(TreeNode *root)
 6         {
 7             // 层序遍历，一旦找到一个叶节点，它肯定是最短的
 8             if (root == NULL)return 0;
 9             queue<tree> qu;
10             tree now = root; // 记录该层的当前节点
11             tree last = root; // 记录该层的最后一个节点
12             int level = 1;
13             int size = 0;
14             qu.push(root);
15             while (!qu.empty())
16             {
17                 now = qu.front(); // 取队首
18                 qu.pop(); // 出队首
19                 size = qu.size();
20                 if (now->left != NULL)qu.push(now->left);
21                 if (now->right != NULL)qu.push(now->right);
22                 // 没有元素进队，说明这是一个叶子节点，找到的第一个叶子节点为最短的
23                 if (size - qu.size() == 0)break;
24                 // last==now，说明当前节点走到了该层的最后一个节点
25                 if (last == now)
26                 {
27                     level++;
28                     // last指向下一层的最后一个节点
29                     if (!qu.empty())last = qu.back();
30                 }
31             }
32             return level;
33         }