Java实现N叉树数据结构

迷南。 2023-10-04 09:04 68阅读 0赞

package MaximumDepthNAryTreeNew;
    
    import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.Queue;
    
    // class representing node of n-ary tree
    class Node {
    	int val;
    	ArrayList<Node> children;
    
    	public Node(int val) {
    		this.val = val;
    		this.children = new ArrayList<>();
    	}
    }
    
    class NumberOfSiblingsOfAGivenNodeInNAryTree {
    
    	public static int maxDepth(Node root) {
    		if (root == null)
    			return 0;
    		int max = 0;
    		for (Node n : root.children) {
    			max = Math.max(max, maxDepth(n));
    		}
    		return max + 1;
    	}
    
    	private static int siblings(Node root, int target) {
    		// if the given node is equals to the root or root is null, return 0
    		if (root == null || root.val == target) {
    			return 0;
    		}
    		// create a queue of nodes
    		Queue<Node> queue = new LinkedList<>();
    		// push the root to queue
    		queue.add(root);
    		// do a BFS of the tree
    		while (!queue.isEmpty()) {
    			// remove one element from the queue
    			Node curr = queue.poll();
    			// traverse its children
    			for (int i = 0; i < curr.children.size(); i++) {
    				// current child
    				Node currChild = curr.children.get(i);
    				// if current child is the target, return (parent's children count - 1)
    				if (currChild.val == target) {
    					return (curr.children.size() - 1);
    				}
    				// add the child to the queue
    				queue.add(currChild);
    			}
    		}
    		// if there is no match, return -1
    		return -1;
    	}
    
    	public static void main(String[] args) {
    		// Example n-ary tree
    		Node root = new Node(51);
    		// children of 51
    		root.children.add(new Node(10));
    		root.children.add(new Node(41));
    		root.children.add(new Node(6));
    		root.children.add(new Node(32));
    		// children of 10
    		root.children.get(0).children.add(new Node(53));
    		// children of 41
    		root.children.get(1).children.add(new Node(95));
    		// children of 6
    		root.children.get(2).children.add(new Node(28));
    		// children of 32
    		root.children.get(3).children.add(new Node(9));
    		root.children.get(3).children.add(new Node(11));
    		// children of 53
    		root.children.get(0).children.get(0).children.add(new Node(5));
    		root.children.get(0).children.get(0).children.add(new Node(7));
    		// children of 11
    		root.children.get(3).children.get(1).children.add(new Node(3));
    		root.children.get(3).children.get(1).children.add(new Node(8));
    		System.out.println(siblings(root, 10));
    		System.out.println(siblings(root, 11));
    		System.out.println(maxDepth(root));
    	}
    }