leetcode 111. 二叉树的最小深度

题目描述：

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7
返回它的最小深度 2.

思路分析：

一开始的思路是直接求二叉树的最小深度，后来发现题目限定了必须是到叶结点的路径长度最短。所以需要判断当前结点是否是叶结点。判断若左子树为空，则返回右子树的到叶子结点的最短路径；否则返回左子树到叶结点的最短路径。

代码：

 /**

  * 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 height(TreeNode* root)

     {

         if(root == nullptr)

             return ;

         if(root->left==nullptr)

             return height(root->right)+;

         if(root->right == nullptr)

             return height(root->left)+;

         int l = height(root->left);

         int r = height(root->right);

         return min(l,r)+;

     }

     int minDepth(TreeNode* root) {

         if(root == nullptr)

             return ;

         return height(root);

     }

 };

巴特西

leetcode 111. 二叉树的最小深度

最新文章

热门文章