N元树Leetcode解决方案的最大深度  


难度级别 易得奖学金
经常问 亚马逊 谷歌 微软
算法 广度优先搜索 编码 深度优先搜索 访谈 面试准备 力码 力码解决方案 N元树

在这个问题上,我们得到了一个 N元树,即允许节点拥有两个以上子节点的树。 我们需要找到离树的根最远的叶子的深度。 这称为最大深度。 请注意,路径的深度是路径上的节点数。

使用案列  

       2

  /    |    \

3      4      6

                \
           
                  9
3

说明:值9的叶子离根最远,深度为 3。 因此,我们打印3。

      2
  
  /      \

3           6   

        /   |   \

      4     7     9
3

说明:值4,7和9的叶子离根最远,深度为 3。 因此,我们打印3。

方法(递归 

通过调用任意节点左右子节点上的递归函数来计算二叉树的最大深度。 类似地,在N元树的情况下,我们可以通过在任何节点的所有子节点上调用递归函数来计算最大深度。 这种方法是递归的,只需要单次传递树即可。

N元树Leetcode解决方案的最大深度Pin

算法

  1. 创建一个功能 maxDepth() 返回其树的最大深度 被传递给它
  2. If 一片空白:
    • 返回0
  3. 初始化变量 最大深度 存储N进制树的最大深度
  4. 对于每一个 孩子 在当前根目录的子级列表中:
    • maximumDepth = max(maxDepth(root.left),maxDepth(root.right))
  5. 回报 最大深度+ 1

N元树Leetcode解决方案最大深度的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;

struct Node
{
    int value;
    vector <Node*> children;

    Node(int val)
    {
        value = val;
        children = {};
    }

    Node(int val , vector <Node*> childList)
    {
        value = val;
        children = childList;
    }
};

int maxDepth(Node* root)
{
    if(root == NULL)
        return 0;
    int maximumDepth = 0;
    for(Node* &child : root->children)
        maximumDepth = max(maximumDepth , maxDepth(child));
    return maximumDepth + 1;
}

int main()
{
    Node* root = new Node(2);
    root->children = {new Node(3) , new Node(4) , new Node(5)};
    root->children[2]->children = {new Node(9)};
    cout << maxDepth(root) << '\n';
    return 0;
}

Java程序

import java.lang.Math;

class Node
{
    int value;
    Node[] children;

    Node(int val)
    {
        value = val;
        children = new Node[]{};
    }

    Node(int val , Node[] childList)
    {
        value = val;
        children = childList;
    }
};

class maximum_depth
{
    public static void main(String args[])
    {
        Node root = new Node(2);
        Node[] a = {new Node(3) , new Node(4) , new Node(5)};
        root.children = a;
        Node[] b = {new Node(9)};
        root.children[2].children = b;
        System.out.println(maxDepth(root));
    }

    static int maxDepth(Node root)
    {
        if(root == null)
            return 0;
        int maximumDepth = 0;
        for(int i = 0 ; i < root.children.length ; i++)
            maximumDepth = Math.max(maximumDepth , maxDepth(root.children[i]));
        return maximumDepth + 1;
    }
}
3

N元树Leetcode解的最大深度的复杂度分析

时间复杂度

O(N),N =当我们遍历整棵树时,N元树的大小。

参见
最少插入以形成回文并允许排列

空间复杂度

上) 因为我们将堆栈帧存储在内存中以进行递归调用。

方法(迭代 

通过使用堆栈或队列来存储节点及其从根开始的深度,我们可以迭代地完成上述过程。 最大深度将是通过此过程获得的所有根的最大深度。 为此,我们使用队列,并将树的所有元素以及它们从根开始的深度推入队列。 我们将每个节点的深度与最大深度进行比较并进行更新。

算法

  1. 创建功能 maxDepth() 与上述方法类似
  2. If  is 空值:
    • 返回0
  3. 初始化 最大深度 存储我们的结果
  4. 初始化队列 分子 包含树节点及其深度
  5. 根 队列中的深度为1
  6. 分子 不为空:
    • 获取前节点及其高度为 前节点 以及 前端节点深度
    • 将项目弹出队列
    • If 前端节点深度 is 更大的最大深度
      1. 更新 最大深度 = 前节点深度
    • If 前节点 is 不为null:
      1. 将所有子项以他们的深度推入队列 前端节点深度 + 1
  7. 回报 最大深度
  8. 打印结果

N元树Leetcode解决方案最大深度的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;

struct Node
{
    int value;
    vector <Node*> children;

    Node(int val)
    {
        value = val;
        children = {};
    }

    Node(int val , vector <Node*> childList)
    {
        value = val;
        children = childList;
    }
};

int maxDepth(Node* root)
{
    if(root == NULL)
        return 0;
    int maximumDepth = 0 , frontNodeDepth;

    queue <pair <Node* , int> > elements;
    elements.push({root , 1});
    Node* frontNode;
    while(!elements.empty())
    {
        frontNode = elements.front().first;
        frontNodeDepth = elements.front().second;
        elements.pop();
        if(frontNodeDepth > maximumDepth)
            maximumDepth = frontNodeDepth;

        if(frontNode != NULL)
        {
            for(Node* &child : frontNode->children)
                elements.push({child , frontNodeDepth + 1});
        }
    }

    return maximumDepth;
}

int main()
{
    Node* root = new Node(2);
    root->children = {new Node(3) , new Node(4) , new Node(5)};
    root->children[2]->children = {new Node(9)};
    cout << maxDepth(root) << '\n';
    return 0;
}

Java程序

import java.lang.Math;
import java.util.*;

class Node
{
    int value;
    Node[] children;

    Node(int val)
    {
        value = val;
        children = new Node[]{};
    }

    Node(int val , Node[] childList)
    {
        value = val;
        children = childList;
    }
};

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

class maximum_depth
{
    public static void main(String args[])
    {
        Node root = new Node(2);
        Node[] a = {new Node(3) , new Node(4) , new Node(5)};
        root.children = a;
        Node[] b = {new Node(9)};
        root.children[2].children = b;
        System.out.println(maxDepth(root));
    }

    static int maxDepth(Node root)
    {
        if(root == null)
            return 0;
        LinkedList <Pair> elements = new LinkedList <>();
        elements.add(new Pair(root , 1));
        Node frontNode;
        int maximumDepth = 0 , frontNodeDepth;

        while(elements.size() > 0)
        {
            frontNode = elements.peek().key;
            frontNodeDepth = elements.peek().value;
            elements.remove();
            if(frontNodeDepth > maximumDepth)
                maximumDepth = frontNodeDepth;

            if(frontNode != null)
            {
                for(int i = 0 ; i < frontNode.children.length ; i++)
                    elements.add(new Pair(frontNode.children[i] , frontNodeDepth + 1));
            }
        }
        return maximumDepth;
    }
}
3

N元树Leetcode解的最大深度的复杂度分析

时间复杂度

上) 当我们再次遍历整棵树时。 N =树的大小

参见
计算每个大小为K的窗口中的不同元素

空间复杂度

上) 因为我们使用队列将树的所有节点及其深度存储在树中。