二叉树的最小深度【C++】【后序遍历】

二叉树的最小深度

http://www.nowcoder.com/questionTerminal/e08819cfdeb34985a8de9c4e6562e724

后序遍历树,这样在回到每个节点时,其节点左右子树的最小深度都已经计算完毕,当前节点的最小深度就等于左右子树中较小深度加一。
递归边界:如果节点是空节点,最小深度返回INT_MAX,如果节点是叶节点,最小深度为1。
时间复杂度O(N),空间复杂度O(N)。

int minDepth(TreeNode* root) {
        if(root == nullptr) {
            return INT_MAX;
        }
        if(root->left == nullptr && root->right == nullptr) {
            return 1;
        }
        int leftDepth = minDepth(root->left);
        int rightDepth = minDepth(root->right);
        int depth = min(leftDepth, rightDepth);    //不会得到depth == INT_MAX的情况
        return depth+1;
    }
    int run(TreeNode* root) {
        if(root == nullptr) {
            return 0;
        }
        return minDepth(root);
    }
全部评论

相关推荐

06-17 21:57
门头沟学院 Java
白友:噗嗤,我发现有些人事就爱发这些,明明已读不回就行了,就是要恶心人
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务