leetcode 111 二叉树最小深度

简介: leetcode 111 二叉树最小深度

111二叉树最小深度


a28462387f8e4e0baec14ad0e46abac9.png

寻找到层数最小的叶子节点,即层数最小的左右指针为空的节点

层次迭代法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
       TreeNode* node ; //迭代节点
        queue<TreeNode*> my_que; //队列
        int result = 0;
        vector<int> min_num;
        if(root == nullptr) return result;
        else // 根节点进队列
        {
            my_que.push(root);
        }
        while(my_que.empty() != 1)
        {
            int size = my_que.size();
            result +=1;
            for(int i=0 ; i<size ; i++) 
            {
                node = my_que.front(); //该层级的点弹出放入数组
                my_que.pop();
                // cout<<node->val<<' '<<node->left<<' '<<node->right<<endl;
                //每一个弹出点的下一个层级左右节点压入队列
                if(node->left != nullptr)    my_que.push(node->left);
                if(node->right != nullptr)   my_que.push(node->right);
                //找到叶子节点
                if(node->left == nullptr && node->right == nullptr)  min_num.push_back(result);
            }
        }
        //排序找到叶子节点所在最小层
        sort(min_num.begin(),min_num.end());
        return min_num[0];
    }
};


递归法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int getdepth(TreeNode* cur)
    {
        if(cur == nullptr) return 0;
        int right_depth , left_depth;
        //左子树为空,直接测量右子树
        if(cur->left == nullptr && cur->right != nullptr)
        {
            right_depth = getdepth(cur->right);
            return 1 + right_depth;
        }else if(cur->left != nullptr && cur->right == nullptr) //右子树为空,直接测量左子树
        {
            left_depth = getdepth(cur->left);
            return 1 + left_depth;
        }else//左右子树都为空或都不为空,左右子树均测量,返回最小值
        {
            left_depth = getdepth(cur->left);
            right_depth = getdepth(cur->right);
            return 1 +  min(left_depth,right_depth);
        }
    }
    int minDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        return getdepth(root);
    }
};


二刷

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == nullptr ) return 0;
        int left_deep = minDepth(root->left);
        int right_deep = minDepth(root->right);
        if(left_deep==0 && right_deep==0) return 0+1 ;
        else if(left_deep == 0 && right_deep != 0) return right_deep+1;
        else if(left_deep != 0 && right_deep == 0) return left_deep+1;
        else return min(left_deep,right_deep)+1; 
    }
};

目录
打赏
0
0
0
0
5
分享
相关文章
|
6月前
|
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
75 6
|
4月前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
39 2
|
4月前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
35 2
|
4月前
【LeetCode 28】102.二叉树的层序遍历
【LeetCode 28】102.二叉树的层序遍历
27 2
|
4月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
33 0
|
4月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
30 0
|
4月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
33 0
|
4月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
38 0
|
4月前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
29 0
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
文章深入探讨了二叉树的层序遍历方法,并展示了如何通过队列实现层序遍历的算法逻辑,同时指出掌握层序遍历技巧可以帮助解决LeetCode上的多道相关题目。
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等