Welcome to Subscribe On Youtube

1522. Diameter of N-Ary Tree

Description

Given a root of an N-ary tree, you need to compute the length of the diameter of the tree.

The diameter of an N-ary tree is the length of the longest path between any two nodes in the tree. This path may or may not pass through the root.

(Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value.)

 

Example 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: 3
Explanation: Diameter is shown in red color.

Example 2:

Input: root = [1,null,2,null,3,4,null,5,null,6]
Output: 4

Example 3:

Input: 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]
Output: 7

 

Constraints:

  • The depth of the n-ary tree is less than or equal to 1000.
  • The total number of nodes is between [1, 104].

Solutions

  • /*
    // 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.
    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.
     * 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
    }
    

All Problems

All Solutions