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
     
       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
     
       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
     
       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
     
       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 也可以用在节点中加入一个域表征层次信息，也可实现