[LeetCode] 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 空节点，dep = 0；

2 叶节点， dep = 1；

3 左子树为空，dep = 1 + 右子树的最小dep

4 右子树为空，dep = 1 + 左子树的最小dep

5 左右字数都非空，dep = min(左子树的最小dep，右子树的最小dep) + 1；

1 递归算法实现：

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     int minDepth(TreeNode *root) {
13         
14         if(root == NULL) return 0;
15         if(root->left == NULL && root->right == NULL) 
16             return 1;
17         if(root->left == NULL)
18             return 1 + minDepth(root->right);
19         if(root->right == NULL)
20             return 1 + minDepth(root->left);
21             
22         return 1 + min(minDepth(root->left), minDepth(root->right));
23     }
24 };

2 迭代实现

在之前的前序遍历的基础上进行修改和减枝

之前的想法是这样，但是发现dep不知何时--，

 1 class Solution {
 2     public:
 3         int minDepth(TreeNode *root) {
 4             ;
 5             if(NULL == root) return 0;
 6 
 7             int minDep = INT_MAX;
 8 
 9             stack<TreNode*> stack;
10 
11             TreeNode *p = root;
12             stack.push(p);
13             int dep = 1;
14 
15             while( !stack.empty())
16             {
17                 p= stack.top();
18                 stack.pop();
19 
20                 if(p->left == NULL && p->right == NULL)
21                 {
22                     minDep = min(minDep, dep);
23                 }
24 
25                 if(p->left != NULL && dep < minDep)
26                 {
27                     dep = dep + 1;
28                     stack.push(p->left);
29                 }
30 
31                 if(pNode->right != NULL && dep < minDep)
32                 {
33                     dep = dep + 1;
34                     stack.push(p->right);
35                 }
36 
37             }
38 
39             return minDep;
40         }
41 
42 };

于是这样，搞定

 1 struct newNode{
 2     TreeNode * node;
 3     int         dep; // 记录当前节点的深度，如果不用这个域，无法或者当前接地啊的深度
 4 };
 5 
 6 class Solution {
 7 public:
 8     int minDepth(TreeNode *root) {
 9         ;
10         if(NULL == root) return 0;
11         
12         int minDep = INT_MAX;
13         
14         stack<newNode*> stack;
15         
16         newNode *p = new newNode;
17         p->node = root;
18         p->dep = 1;
19         stack.push(p);
20         
21         while( !stack.empty())//前序遍历框架  超级有用！！！
22         {
23             p= stack.top();
24             stack.pop();
25             
26             TreeNode *pNode = p->node;
27             int dep = p->dep;
28             
29                 
30             if(pNode->left == NULL && pNode->right == NULL) //叶子节点
31             {
32                 minDep = min(minDep, dep); //退出条件
33             }
34             
35             if(pNode->left != NULL && dep < minDep) //减枝
36             {
37                 newNode *tmp = new newNode;
38                 tmp->node = pNode->left;
39                 tmp->dep = dep + 1;
40                 stack.push(tmp);
41             }
42             
43             if(pNode->right != NULL && dep < minDep) //减枝
44             {
45                 newNode *tmp = new newNode;
46                 tmp->node = pNode->right;
47                 tmp->dep = dep + 1;
48                 stack.push(tmp);
49             }
50             
51         }
52         
53         return minDep;
54     }
55     
56 };

3 前面考虑的都是深度遍历，即DFS，其实也可以用BFS，来解决，BFS中第一次遇到的也节点就是结果，//层序遍历，碰到第一个叶子节点就停止,NULL作为每一层节点的分割标志

 1 class Solution {
 2     public:
 3         int minDepth(TreeNode *root) {
 4             if(NULL == root) return 0;
 5 
 6             queue<TreeNode*> queue;
 7 
 8             TreeNode *p = root;
 9             queue.push(p);
10             queue.push(NULL);
11             int dep = 1;
12 
13             while( !queue.empty())
14             {   
15                 p= queue.front();
16                 queue.pop();
17 
18                 if(p == NULL)
19                 {   
20                     dep++;
21                     if(!queue.empty())
22                         queue.push(NULL);
23                     continue;
24                 }   
25 
26                 if(p->left == NULL && p->right == NULL)
27                     return dep;
28 
29                 if(p->left != NULL )
30                 {   
31                     queue.push(p->left);
32                 }   
33 
34                 if(p->right != NULL )
35                 {   
36                     queue.push(p->right);
37                 }
38 
39             }
40 
41             return dep;
42         }
43 
44 };

4 用BFS，也可以用两个队列，队列交换时深度加一，也可实现。

 1 class Solution {
 2     public:
 3         int minDepth(TreeNode *root) {
 4             if(NULL == root) return 0;
 5 
 6             queue<TreeNode*> cur, next;
 7 
 8             TreeNode *p = root;
 9             cur.push(p);
10             int dep = 1;
11 
12             while( !cur.empty())
13             {
14                 p= cur.front();
15                 cur.pop();
16 
17                 if(p->left == NULL && p->right == NULL)
18                     return dep;
19 
20                 if(p->left != NULL )
21                 {
22                     next.push(p->left);
23                 }
24 
25                 if(p->right != NULL )
26                 {
27                     next.push(p->right);
28                 }
29 
30                 if(cur.empty() && !next.empty())
31                 {
32                     swap(cur, next);
33                     dep++;
34                 }
35             }
36 
37             return dep;
38         }
39 
40 };

5 也可以用在节点中加入一个域表征层次信息，也可实现