解法二: 递归 遇到叶子节点不递归, 否则接着往子树递归, 每次递归层数加 1
- /**
- * Definition for a binary tree node.
- * struct TreeNode {
- * int val;
- * TreeNode *left;
- * TreeNode *right;
- * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
- * };
- */
- class Solution {
- public:
- int minDepth(TreeNode* root) {
- if(root==NULL) return 0;//root 节点是空节点, 深度为 0
- int a=1;
- if(!root->right && !root->left) return 1;// 只有一个节点, 深度就是 1
- if(!root->left){// 左节点空, 右节点非空, 在右子树里面找最近的叶子节点
- return 1+minDepth(root->right);
- }
- if(!root->right){// 右节点空, 左节点非空, 在左子树里面找最近的叶子节点
- return 1+minDepth(root->left);
- }
- // 两个节点都非空, 那就继续迭代下一层
- return 1+min(minDepth(root->left),minDepth(root->right));
- }
- };
方法二:
BFS, 广度优先搜索 每次把一层节点压入队列, 同时判断这些节点中是否含有叶子节点 (即左右指针都为空), 若有, 说明找到了最近的那个叶子节点, 返回层数.
- class Solution {
- public:
- int minDepth(TreeNode* root) {
- if(root==NULL) return 0; // 判空
- queue<pair<TreeNode*,int>> que; // 把节点和所在的层数绑定
- que.push(make_pair(root,1)); // 压入根节点, 层数为 1
- while(1)
- {
- TreeNode* node=que.front().first; // 当前节点
- int level=que.front().second; // 层数
- que.pop();
- if (!node->left && !node->right) return level;// 遇到叶子节点
- if(node->left) // 压入左节点
- que.push(make_pair(node->left,level+1));
- if(node->right)// 压入右节点
- que.push(make_pair(node->right,level+1));
- }
- }
- };
来源: http://www.bubuko.com/infodetail-3100519.html