Java教程

1522. Diameter of N-Ary Tree

本文主要是介绍1522. Diameter of N-Ary Tree,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

This is a similar problem with "543. Diameter of Binary Tree", the only difference is 543 is a binary tree, and 1522 is an n_ary tree.

For 1522, we need to get the two longest path passing through the node, following is the solution:

    private int res = 0;
    public int diameter(Node root) {
        helper(root);
        return res;
    }
    
    private int helper(Node root){
        if(root.children==null)
            return 0;
        int max1 = 0, max2 = 0;
        List<Node> children = root.children;
        for(Node child: children){
            int len = helper(child)+1;
            if(len>max1){      //find the longest two paths
                max2 = max1;     
                max1 = len;
            }else if(len>max2){
                max2 = len;
            }
        }
        res = Math.max(res, max1+max2);
        return max1;
    }
这篇关于1522. Diameter of N-Ary Tree的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!