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.
/** * 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) { // Start typing your C/C++ solution below // DO NOT write int main() function if(root == NULL) return 0; int leftNum = 1 + minDepth(root->left) ; int rightNum = 1 + minDepth(root->right); //排除非叶子节点的情况 if(root->left == NULL) return rightNum; if(root->right == NULL ) return leftNum ; int result = leftNum < rightNum ? leftNum: rightNum ; return result ; } };
重写后 :主要是为了强化路径的定义而重写
class Solution { public: void DFS(TreeNode * root, int len){ if(root->left== NULL && root->right == NULL ){ res = res < len ? res : len; return; } if(root->left != NULL) DFS(root->left, len +1); if(root->right != NULL) DFS(root->right, len+1); } int minDepth(TreeNode *root) { // Start typing your C/C++ solution below // DO NOT write int main() function if(root == NULL ) return 0; res = INT_MAX; DFS(root, 1); return res; } private: int res; };