力扣算法题—111.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.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

return its minimum depth = 2.

Solution:

　　使用深度遍历和广度遍历

 class Solution {

 private:

     int minLevel = INT32_MAX;

 public:

     int minDepth(TreeNode* root) {

         if (root == nullptr)return ;

         //return BFS(root);

         int res = INT32_MAX;

         DFS(root, , res);

         return res;

     }

     int BFS(TreeNode* root)

     {

         queue<TreeNode*>q;

         q.push(root);

         int level = ;

         while (!q.empty())

         {

             queue<TreeNode*>temp;

             ++level;

             while (!q.empty())

             {

                 TreeNode* p = q.front();

                 q.pop();

                 if (p->left == nullptr && p->right == nullptr)return level;

                 if (p->left != nullptr)temp.push(p->left);

                 if (p->right != nullptr)temp.push(p->right);

             }

             q = temp;

         }

         return level;

     }

     void DFS(TreeNode* root, int level, int &res)

     {

         if (root->left == nullptr && root->right == nullptr) {

             res = res > level ? level : res;

             return;

         }

         if (root->left != nullptr)DFS(root->left, level + , res);

         if (root->right != nullptr)DFS(root->right, level + , res);

     }

 };

巴特西

力扣算法题—111.Minimum Depth of Binary Tree

最新文章

热门文章