Question

1522. N 叉树的直径

English Version

题目描述

给定一棵 N 叉树 的根节点 root ，计算这棵树的直径长度。

N 叉树的直径指的是树中任意两个节点间路径中 最长 路径的长度。这条路径可能经过根节点，也可能不经过根节点。

_（N 叉树的输入序列以层序遍历的形式给出，每组子节点用 null 分隔）_

 

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：3
解释：直径如图中红线所示。

示例 2：

输入：root = [1,null,2,null,3,4,null,5,null,6]
输出：4

示例 3：

输入: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出: 7

 

提示：

• N 叉树的深度小于或等于 1000 。
• 节点的总个数在 [0, 10^4] 间。

解法

方法一

"""
# Definition for a Node.
class Node:
  def __init__(self, val=None, children=None):
    self.val = val
    self.children = children if children is not None else []
"""


class Solution:
  def diameter(self, root: 'Node') -> int:
    """
    :type root: 'Node'
    :rtype: int
    """

    def dfs(root):
      if root is None:
        return 0
      nonlocal ans
      m1 = m2 = 0
      for child in root.children:
        t = dfs(child)
        if t > m1:
          m2, m1 = m1, t
        elif t > m2:
          m2 = t
      ans = max(ans, m1 + m2)
      return 1 + m1

    ans = 0
    dfs(root)
    return ans

/*
// Definition for a Node.
class Node {
  public int val;
  public List<Node> children;


  public Node() {
    children = new ArrayList<Node>();
  }

  public Node(int _val) {
    val = _val;
    children = new ArrayList<Node>();
  }

  public Node(int _val,ArrayList<Node> _children) {
    val = _val;
    children = _children;
  }
};
*/

class Solution {
  private int ans;

  public int diameter(Node root) {
    ans = 0;
    dfs(root);
    return ans;
  }

  private int dfs(Node root) {
    if (root == null) {
      return 0;
    }
    int m1 = 0, m2 = 0;
    for (Node child : root.children) {
      int t = dfs(child);
      if (t > m1) {
        m2 = m1;
        m1 = t;
      } else if (t > m2) {
        m2 = t;
      }
    }
    ans = Math.max(ans, m1 + m2);
    return 1 + m1;
  }
}

/*
// Definition for a Node.
class Node {
public:
  int val;
  vector<Node*> children;

  Node() {}

  Node(int _val) {
    val = _val;
  }

  Node(int _val, vector<Node*> _children) {
    val = _val;
    children = _children;
  }
};
*/

class Solution {
public:
  int ans;

  int diameter(Node* root) {
    ans = 0;
    dfs(root);
    return ans;
  }

  int dfs(Node* root) {
    if (!root) return 0;
    int m1 = 0, m2 = 0;
    for (Node* child : root->children) {
      int t = dfs(child);
      if (t > m1) {
        m2 = m1;
        m1 = t;
      } else if (t > m2)
        m2 = t;
    }
    ans = max(ans, m1 + m2);
    return 1 + m1;
  }
};

/**
 * Definition for a Node.
 * type Node struct {
 *   Val int
 *   Children []*Node
 * }
 */

func diameter(root *Node) int {
  ans := 0
  var dfs func(root *Node) int
  dfs = func(root *Node) int {
    if root == nil {
      return 0
    }
    m1, m2 := 0, 0
    for _, child := range root.Children {
      t := dfs(child)
      if t > m1 {
        m2, m1 = m1, t
      } else if t > m2 {
        m2 = t
      }
    }
    ans = max(ans, m1+m2)
    return 1 + m1
  }
  dfs(root)
  return ans
}

方法二

"""
# Definition for a Node.
class Node:
  def __init__(self, val=None, children=None):
    self.val = val
    self.children = children if children is not None else []
"""


class Solution:
  def diameter(self, root: 'Node') -> int:
    """
    :type root: 'Node'
    :rtype: int
    """

    def build(root):
      nonlocal d
      if root is None:
        return
      for child in root.children:
        d[root].add(child)
        d[child].add(root)
        build(child)

    def dfs(u, t):
      nonlocal ans, vis, d, next
      if u in vis:
        return
      vis.add(u)
      for v in d[u]:
        dfs(v, t + 1)
      if ans < t:
        ans = t
        next = u

    d = defaultdict(set)
    vis = set()
    build(root)
    ans = 0
    next = None
    dfs(root, 0)
    vis.clear()
    dfs(next, 0)
    return ans

/*
// Definition for a Node.
class Node {
  public int val;
  public List<Node> children;


  public Node() {
    children = new ArrayList<Node>();
  }

  public Node(int _val) {
    val = _val;
    children = new ArrayList<Node>();
  }

  public Node(int _val,ArrayList<Node> _children) {
    val = _val;
    children = _children;
  }
};
*/

class Solution {
  private Map<Node, Set<Node>> g;
  private Set<Node> vis;
  private Node next;
  private int ans;

  public int diameter(Node root) {
    g = new HashMap<>();
    build(root);
    vis = new HashSet<>();
    next = root;
    ans = 0;
    dfs(next, 0);
    vis.clear();
    dfs(next, 0);
    return ans;
  }

  private void dfs(Node u, int t) {
    if (vis.contains(u)) {
      return;
    }
    vis.add(u);
    if (t > ans) {
      ans = t;
      next = u;
    }
    if (g.containsKey(u)) {
      for (Node v : g.get(u)) {
        dfs(v, t + 1);
      }
    }
  }

  private void build(Node root) {
    if (root == null) {
      return;
    }
    for (Node child : root.children) {
      g.computeIfAbsent(root, k -> new HashSet<>()).add(child);
      g.computeIfAbsent(child, k -> new HashSet<>()).add(root);
      build(child);
    }
  }
}

/*
// Definition for a Node.
class Node {
public:
  int val;
  vector<Node*> children;

  Node() {}

  Node(int _val) {
    val = _val;
  }

  Node(int _val, vector<Node*> _children) {
    val = _val;
    children = _children;
  }
};
*/

class Solution {
public:
  unordered_map<Node*, unordered_set<Node*>> g;
  unordered_set<Node*> vis;
  Node* next;
  int ans;

  int diameter(Node* root) {
    build(root);
    next = root;
    ans = 0;
    dfs(next, 0);
    vis.clear();
    dfs(next, 0);
    return ans;
  }

  void dfs(Node* u, int t) {
    if (vis.count(u)) return;
    vis.insert(u);
    if (ans < t) {
      ans = t;
      next = u;
    }
    if (g.count(u))
      for (Node* v : g[u])
        dfs(v, t + 1);
  }

  void build(Node* root) {
    if (!root) return;
    for (Node* child : root->children) {
      g[root].insert(child);
      g[child].insert(root);
      build(child);
    }
  }
};

/**
 * Definition for a Node.
 * type Node struct {
 *   Val int
 *   Children []*Node
 * }
 */

func diameter(root *Node) int {
  g := make(map[*Node][]*Node)
  vis := make(map[*Node]bool)
  next := root
  ans := 0
  var build func(root *Node)
  build = func(root *Node) {
    if root == nil {
      return
    }
    for _, child := range root.Children {
      g[root] = append(g[root], child)
      g[child] = append(g[child], root)
      build(child)
    }
  }
  build(root)
  var dfs func(u *Node, t int)
  dfs = func(u *Node, t int) {
    if vis[u] {
      return
    }
    vis[u] = true
    if t > ans {
      ans = t
      next = u
    }
    if vs, ok := g[u]; ok {
      for _, v := range vs {
        dfs(v, t+1)
      }
    }
  }
  dfs(next, 0)
  vis = make(map[*Node]bool)
  dfs(next, 0)
  return ans
}