18

100天iOS数据结构与算法实战 Day17-二叉树的算法实战 Minimum Depth of a Binary Tree

 4 years ago
source link: https://www.tuicool.com/articles/6j2ANbN
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time. 
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.

Z77NZfq.jpg!web

主要代码 

- (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资源

https://github.com/renmoqiqi/100-Days-Of-iOS-DataStructure-Algorithm/tree/master/Day17

建了个微信群方便大家交流

R3qYbau.jpg!web

最重要的时刻

你们在文章末尾点的每一个 在看， 是对我的支持。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK