FilesExpand file tree

 master

/

NaryTreePostorderTraversal590.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

58 lines (50 loc) · 1.38 KB

 master

/

NaryTreePostorderTraversal590.java

Copy path

Top

File metadata and controls

• Code
• Blame

58 lines (50 loc) · 1.38 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

/**

* Given an n-ary tree, return the postorder traversal of its nodes' values.

*

* For example, given a 3-ary tree:

* https://leetcode.com/static/images/problemset/NaryTreeExample.png

*

* Return its postorder traversal as: [5,6,3,2,4,1].

*

* Note: Recursive solution is trivial, could you do it iteratively?

*/

/*

// Definition for a Node.

class Node {

public int val;

public List<Node> children;

public Node() {}

public Node(int _val,List<Node> _children) {

val = _val;

children = _children;

}

};

*/

public class NaryTreePostorderTraversal590 {

public List<Integer> postorder(Node root) {

List<Integer> res = new ArrayList<>();

helper(root, res);

return res;

}

private void helper(Node root, List<Integer> res) {

if (root == null) return;

for (Node child: root.children) {

helper(child, res);

}

res.add(root.val);

}

public List<Integer> postorder2(Node root) {

LinkedList<Integer> res = new LinkedList<>();

if (root == null) return res;

Stack<Node> stack = new Stack<>();

stack.push(root);

while (!stack.isEmpty()) {

Node curr = stack.pop();

res.addFirst(curr.val);

for (Node child: curr.children) {

stack.add(child);

}

}

return res;

}

}