LeetCode 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.

本题思路:

1. 每进入一层用一个变量(这里是levelNum)记录当前从根节点到这一层节点的节点数

2. 当到达叶子节点的时候,就记录当前最小深度overall

2. 当所有的叶子节点都到达一遍之后,就得到了最终最小深度overall。

有点动态规划法的影子。

[cpp][/cpp] view plaincopyprint?

  1. class Solution {
  2. public:
  3.     int minDepth(TreeNode *root) {
  4.         if(root == nullptr) return 0;
  5.         int overall = INT_MAX;
  6.         int levelNum = 0;
  7.         minD(root, overall, levelNum);
  8.         return overall;
  9.     }
  10.     void minD(TreeNode *node, int &overall, int levelNum)
  11.     {
  12.         if(node == nullptr) return;
  13.         levelNum++;
  14.         minD(node->left, overall, levelNum);
  15.         minD(node->right, overall, levelNum);
  16.         if(node->left==nullptr && node->right==nullptr)
  17.             overall = min(overall,levelNum);
  18.     }
  19. };

标签