美文网首页
LeetCode-MinimumDepthOfBinaryTre

LeetCode-MinimumDepthOfBinaryTre

作者: 杨柳岸小鹏残月 | 来源:发表于2017-07-16 22:51 被阅读4次

    题目:

    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.

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    

    分析:
    查找二叉树的最小深度
    分2种情况:
    如果结点为NULL,返回0
    否则,返回1+左右结点的最小深度
    但这里有个地方需要注意,如果左右结点有一个为空,则应该返回1+另一个不为空的深度
    如果左右节点都为空直接返回1
    总结一下就是

    if(l==0 || r==0)
        return 1+l+r;
    

    AC代码

    class Solution {
    public:
        int minDepth(TreeNode* root) {
            if(!root)
                return 0;
            int l = minDepth(root->left);
            int r = minDepth(root->right);
            if(l==0 || r==0)
                return 1+l+r;
            return 1+min(l,r);
        }
    };
    

    相关文章

      网友评论

          本文标题:LeetCode-MinimumDepthOfBinaryTre

          本文链接:https://www.haomeiwen.com/subject/ocbxkxtx.html