二叉树的算法实战 Minimum Depth of a Binary Tree

迷南。 2022-01-19 06:09 123阅读 0赞

## 题目 ##

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.
    复制代码

## 主要代码 ##

- (int)minimumDepth:(DSTreeNode *)root
    {
        //1
        if (root == nil) {
            return 0;
        }
        //2
        if (root.leftChild == nil) {
            return [self minimumDepth:root.rightChild]+1;
    
        }
        //3
        if (root.rightChild == nil) {
            return [self minimumDepth:root.leftChild]+1;
    
        }
        //4
        return MIN([self minimumDepth:root.leftChild], [self minimumDepth:root.rightChild])+1;
    
    }
    复制代码

## 思路 ##

1.  遍历二叉树的每个节点，如果当前节点是叶子节点，则返回1。
2.  如果不是叶子节点，且左子树为null，然后递归右子树。
3.  如果不是叶子节点且右子树为null，然后递归左子树。
4.  如果不是叶子节点，且左右子树不为null那么取递归后两者最小值。

## 小结 ##

*  由于遍历树的每个节点，因此时间复杂度是O（n）。
 *  当然还有其他不错的思路比如用层级遍历的方法，返回第一个遇到叶子节点的深度。

## GitHubDemo资源 ##

[github.com/renmoqiqi/1…][github.com_renmoqiqi_1]

转载于:https://juejin.im/post/5cfdb625f265da1baf7cdfcd

[github.com_renmoqiqi_1]: https://link.juejin.im?target=https%3A%2F%2Fgithub.com%2Frenmoqiqi%2F100-Days-Of-iOS-DataStructure-Algorithm%2Ftree%2Fmaster%2FDay17