N-ary 题型总结

本文主要是介绍N-ary 题型总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

N-ary题型，最近问的比较多。总结一下。

N-ary Tree Preorder Traversal

思路：跟BST的一样，preorder: current, left, right, 那么就是push 右边再push左边，N-try不一样的就是要从右边一直push，到左边；

class Solution {// preorder, current, left, right;public List<Integer> preorder(Node root) {List<Integer> list = new ArrayList<>();if(root == null) {return list;}Stack<Node> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()) {Node node = stack.pop();list.add(node.val);List<Node> children = node.children;for(int i = children.size() - 1; i >= 0; i--) {stack.push(children.get(i));}}return list;}
}

N-ary Tree Postorder Traversal

Pre-order is: current, left, right;

our goal is: left, right, current.

we can do: current, right, left. 这里就是先push left，再push right，就是答案；加的时候逆序加就可以了。

 反过来就是: left, right, current,

用linkedlist addfirst，就是逆序加result，这样就可以是答案了；

/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
};
*/class Solution {public List<Integer> postorder(Node root) {List<Integer> list = new LinkedList<Integer>();Stack<Node> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()) {Node node = stack.pop();if(node != null) {list.add(0, node.val);for(int i = 0; i < node.children.size(); i++) {stack.push(node.children.get(i));}}}return list;}
}

N-ary Tree Level Order Traversal 就是一个Queue的level order traverse；

class Solution {public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> lists = new ArrayList<List<Integer>>();if(root == null) {return lists;}Queue<Node> queue = new LinkedList<Node>();queue.offer(root);while(!queue.isEmpty()) {int size = queue.size();List<Integer> list = new ArrayList<Integer>();for(int i = 0; i < size; i++) {Node node = queue.poll();list.add(node.val);for(Node child: node.children) {queue.offer(child);}}lists.add(list);}return lists;}
}

Maximum Depth of N-ary Tree DFS, divide and conquer,每次计算下面返回上来的最大值，然后最大值+ 1;

class Solution {public int maxDepth(Node root) {if(root == null) {return 0;}int depth = 0;for(Node child: root.children) {depth = Math.max(depth, maxDepth(child));}return depth + 1;}
}

BFS Level order

class Solution {public int maxDepth(Node root) {if(root == null) {return 0;}Queue<Node> queue = new LinkedList<Node>();queue.offer(root);int depth = 0;while(!queue.isEmpty()) {int size = queue.size();for(int i = 0; i < size; i++) {Node node = queue.poll();for(Node child: node.children) {queue.offer(child);}}depth++;}return depth;}
}

 Serialize and Deserialize N-ary Tree 做这个题目之前，先明白 Serialize and Deserialize Binary Tree 和 Serialize and Deserialize BST 区别和异同，Serialize and Deserialize Binary Tree 因为是BT，没有相互之前的大小关系，所以要serialize full tree，连NULL都要serialize进去，但是BST不同，BST有左右的大小关系，所以只用serialize 有value的node就行，两个都是用queue来serialize，然后用queue来build。N-ary Tree跟BT不同的是，他有children；不能用preorder去serilize，只能用level order去serilize。不同的是，N-ary后面有child的size信息，我们也serilize进去，那么desrilize的时候，用两个queue，一个存当前node的queue，一个存node的child size信息，那么，如果size是n，那么后面2 * n个string (node + child size)，都是当前node的child；每个node都有自己的child信息；Serilize用level order，(跟BT不一样, BT是用)一行一行的serilize，deserilize也是一层一层的build；

/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
};
*/class Codec {// Encodes a tree to a single string.private String NULL = "NULL";private String DILIMITER = ",";public String serialize(Node root) {if(root == null) {return NULL;}StringBuilder sb = new StringBuilder();Queue<Node> queue = new LinkedList<Node>();queue.offer(root);while(!queue.isEmpty()) {Node head = queue.poll();sb.append(head.val).append(DILIMITER).append(head.children.size()).append(DILIMITER);for(Node child: head.children) {queue.offer(child);}}return sb.toString();}// Decodes your encoded data to tree.public Node deserialize(String data) {if(data == null || data.equals(NULL)) {return null;}String[] splits = data.split(DILIMITER);Queue<Node> nqueue = new LinkedList<Node>();Queue<Integer> cqueue = new LinkedList<Integer>();Node root = new Node(Integer.parseInt(splits[0]));int size = Integer.parseInt(splits[1]);nqueue.offer(root);cqueue.offer(size);int index = 2;while(!nqueue.isEmpty()) {Node node = nqueue.poll();int nsize = cqueue.poll();node.children = new ArrayList<Node>();for(int i = 0; i < nsize; i++) {Node newnode = new Node(Integer.parseInt(splits[index++]));int newsize = Integer.parseInt(splits[index++]);node.children.add(newnode);nqueue.offer(newnode);cqueue.offer(newsize);}}return root;}
}// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

这篇关于N-ary 题型总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---