Title: N-ary Tree Preorder Traversal Source: leetcode.com
Given an n-ary tree, return the preorder traversal of its nodes’ values.
For example, given a 3-ary tree:
A 3-ary tree
Return its preorder traversal as: [1,3,5,6,2,4].
Note:
Recursive solution is trivial, could you do it iteratively?
You could find another explanation/ problem related to Preorder Traversal here.
Java solution (Recursive)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
/* https://leetcode.com/problems/n-ary-tree-preorder-traversal/description/ */ import java.util.List; import java.util.ArrayList; public class NaryPreorderTraversal { public static void main(String[] args) { Node node5 = new Node(5); Node node6 = new Node(6); Node node3 = new Node(3); node3.children = new ArrayList<>(); node3.children.add(node5); node3.children.add(node6); Node node2 = new Node(2); Node node4 = new Node(4); Node node1 = new Node(1); node1.children = new ArrayList<>(); node1.children.add(node3); node1.children.add(node2); node1.children.add(node4); NaryPreorderTraversal n = new NaryPreorderTraversal(); List<Integer> list = n.preorder(node1); System.out.println(list); } public List<Integer> preorder(Node root) { List<Integer> list = new ArrayList<>(); helper(root, list); return list; } public void helper(Node root, List<Integer> list) { if(root==null) return; list.add(root.val); if(root.children!=null) { for(Node child : root.children) { helper(child, list); } } } } class Node { public int val; public List<Node> children; public Node() {} public Node(int val) { this.val = val; } public Node(int _val,List<Node> _children) { val = _val; children = _children; } } |
If you think closely about the recursive solution, what we are essentially doing is…
While parsing current node, we first add it’s value to the result list and then move on to each child turn by turn, in left to right order, parsing it as the next current node.
So, to get to an iterative solution, what we need to have is a stack where children to current node could be placed for parsing next and the catch is that they need to be put in reverse order so that the left most child becomes first candidate for parsing.
Python solution (Iterative)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
''' https://leetcode.com/problems/n-ary-tree-preorder-traversal/ ''' """ # Definition for a Node. class Node(object): def __init__(self, val, children): self.val = val self.children = children """ class Solution(object): def preorder(self, root): """ :type root: Node :rtype: List[int] """ stack = root and [root] res = [] while stack: node = stack.pop() res.append(node.val) stack.extend(node.children[::-1]) return res |
can you tell me why my solution fails for input
[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]
it says that the output is [1,3,5,6,2,4,1,2,3,6,7,11,14,4,8,12,5,9,13,10]
and expected is
[1,2,3,6,7,11,14,4,8,12,5,9,13,10]
when i saw the solution they are using extend functionality in python
Hi Micky,
Your solution fails because of the way you’re declared you res variable.
This definition makes the res variable to be shared by all instances of Solution class (if you know Java it’s similar to static variables in it).
So, in order to make your code work as expected all you need to do is make res a Data member/ instance variable.
More specifically, define like this: