二叉树Leetcode解决方案的最小深度  


难度级别 易得奖学金
经常问 亚马逊 Apple Facebook
算法 二叉树 广度优先搜索 编码 深度优先搜索 访谈 面试准备 力码 力码解决方案

在这个问题中,我们需要找到从根到给定叶子中任何叶子的最短路径的长度 二叉树。 注意,这里的“路径长度”是指从根节点到叶节点的节点数。 该长度称为二叉树的最小深度。

使用案列  

输入

二叉树Leetcode解决方案的最小深度Pin

 

 

 

 

 

 

 

2

说明

最短路径是: 2年1月XNUMX日-> XNUMX年XNUMX月XNUMX日 ,长度为2

输入

 

 

 

 

 

 

 

3

说明

最短路径是: 1-> 2-> 3,长度为3

方法(递归)  

这个问题在结构上与找到二叉树的高度相同,但是在这种情况下,我们需要找到根与树中任何叶子之间的最小高度/深度。 我们可以使用以下方法检索根的左和右子树的最小深度 深度优先搜索(DFS) 然后返回两个深度中的最小值。 我们需要考虑某些情况,其中一个节点的左子树和右子树中的任意一个是 。 如果左边的子树是 NULL, 它将返回等于的高度 但是由于我们在此子树中未找到任何叶子,因此 将是一个错误的答案。 因此,我们仅需要在调用了该节点的节点时调用该递归函数即可。 不是 空值。

参见
Pascal的Triangle II Leetcode解决方案

算法

  1. 创建一个功能 minDepth() 返回所传递根的最小深度
  2. 如果根是 , 返回
  3. 如果两个 以及 子树是 ,返回1
  4. 如果左边的子树是 , 返回 1 + minDepth(root-> right)
  5. 否则,如果正确的子树是 , 返回 1 + minDepth(root-> left)
  6. 返回1 +最小值(最小深度(root-> left), 最小深度(root-> right))

二叉树Leetcode解决方案最小深度的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

int minDepth(treeNode* root)
{
    if(root == NULL)
        return 0;
    if(root->left == NULL && root->right == NULL)
        return 1;
    if(root->left == NULL)
        return 1 + minDepth(root->right);
    if(root->right == NULL)
        return 1 + minDepth(root->left);
    return 1 + min(minDepth(root->left) , minDepth(root->right));
}

int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(1);
    root->right = new treeNode(3);
    root->right->left = new treeNode(4);
    root->right->right = new treeNode(5);
    cout << minDepth(root) << '\n';
}

Java程序

import java.util.*;

class treeNode
{
    int value;
    treeNode left, right;
    public treeNode(int x)
    {
        value = x;
        left = right = null;
    }
}

class Pair
{
    treeNode key;
    int value;

    Pair(treeNode root , int val)
    {
        key = root;
        value = val;
    }
}

class Minimum_Depth_Of_A_Binary_Tree
{
    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.right = new treeNode(3);
        root.right.left = new treeNode(4);
        root.right.right = new treeNode(5);
        System.out.println(minDepth(root));
    }

    static int minDepth(treeNode root)
    {
        if(root == null)
            return 0;
        if(root.left == null && root.right == null)
            return 1;
        if(root.left == null)
            return 1 + minDepth(root.right);
        if(root.right == null)
            return 1 + minDepth(root.left);
        return 1 + Math.min(minDepth(root.left) , minDepth(root.right));

    }
}
2

二叉树Leetcode解的最小深度的复杂性分析

时间复杂度

上),即使在最坏的情况下,我们也要遍历整棵树。

空间复杂度

上)。 当二叉树倾斜时,递归堆栈帧可能会占用高达O(N)的空间。

参见
生成具有奇数计数的字符的字符串Leetcode解决方案

方法(迭代)  

我们可以使用 广度优先搜索(BFS) 查找作为叶子的第一个节点,并从根返回其深度。 我们可以使用队列来存储一对节点及其从根节点开始的深度。 当我们收到一个叶子节点时,我们返回它的深度。

算法

  1. 如果root是 , 返回
  2. 初始化一对由树节点和整数组成的队列
  3. 将根节点以其深度推入队列 1
  4. 当队列不为空时:
    • 检索前端队列元素的深度和节点地址
    • 将项目弹出队列
    • 如果前端节点是 ,返回其深度
    • 以及 树的节点,如果它们是 不是
  5. 退货 -1 在函数返回整数时保持程序的语法

二叉树Leetcode解决方案最小深度的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

int minDepth(treeNode* root)
{
    if(root == NULL)
        return 0;
    queue < pair <treeNode* , int> > q;
    q.push({root , 1});

    treeNode* frontNode;
    int depth;

    while(!q.empty())
    {
        frontNode = q.front().first;
        depth = q.front().second;
        q.pop();

        if(frontNode->left == NULL && frontNode->right == NULL)
            return depth;

        if(frontNode->left != NULL)
            q.push({frontNode->left , depth + 1});

        if(frontNode->right != NULL)
            q.push({frontNode->right , depth + 1});
    }
    return -1;
}

int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(1);
    root->right = new treeNode(3);
    root->right->left = new treeNode(4);
    root->right->right = new treeNode(5);
    cout << minDepth(root) << '\n';
}


Java程序

import java.util.*;

class treeNode
{
    int value;
    treeNode left, right;
    public treeNode(int x)
    {
        value = x;
        left = right = null;
    }
}

class Pair
{
    treeNode key;
    int value;

    Pair(treeNode root , int val)
    {
        key = root;
        value = val;
    }
}

class Minimum_Depth_Of_A_Binary_Tree
{
    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.right = new treeNode(3);
        root.right.left = new treeNode(4);
        root.right.right = new treeNode(5);
        System.out.println(minDepth(root));
    }

    static int minDepth(treeNode root)
    {
        if(root == null)
            return 0;
        LinkedList <Pair> q = new LinkedList<>();
        q.add(new Pair(root , 1));

        treeNode frontNode;
        int depth;

        while(q.size() > 0)
        {
            frontNode = q.peek().key;
            depth = q.peek().value;

            q.remove();

            if(frontNode.left == null && frontNode.right == null)
                return depth;

            if(frontNode.left != null)
                q.add(new Pair(frontNode.left , depth + 1));

            if(frontNode.right != null)
                q.add(new Pair(frontNode.right , depth + 1));
        }
        return -1;
    }
}
2

二叉树Leetcode解的最小深度的复杂性分析

时间复杂度

上),当我们再次遍历整棵树时。

参见
商店Leetcode解决方案中的最终价格具有特别折扣

空间复杂度

上),因为我们使用队列来存储每个节点的详细信息。