1.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.
2.題目要求:求二叉樹的最小深度即最短路徑的節(jié)點個數(shù)摄杂。
3.方法:用遞歸的方法坝咐,深度優(yōu)先搜索DFS來完成。
4.代碼:
/**
Definition for binary tree
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;
if (root->left == NULL && root->right == NULL) return 1;if (root->left == NULL) return minDepth(root->right) + 1; else if (root->right == NULL) return minDepth(root->left) + 1; else return 1 + min(minDepth(root->left), minDepth(root->right));
}
};