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.
思路:
首先要区分两种结点:非leaf的结点和leaf的结点。leaf结点的左右子树均为空。
然后对树进行深度优先搜索的同时记录树的当前深度,发现leaf结点时将深度和已知的最小深度比较。
题解:
/** * 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 min_depth; void minDepthProc(TreeNode* node, int depth) { if (node == nullptr) return; if (node->left == nullptr && node->right == nullptr) { // this is a leaf node if (depth < min_depth) min_depth = depth; return; } minDepthProc(node->left, depth + 1); minDepthProc(node->right, depth + 1); } int minDepth(TreeNode *root) { if (root == nullptr) return 0; min_depth = 9999999; // should be std::numeric_limits<int>::max(); minDepthProc(root, 1); return min_depth; } };