LeetCode590

今天的题目如下

1.递归解法，思路较为简单

 1 /*
 2 // Definition for a Node.
 3 class Node {
 4     public int val;
 5     public List children;
 6 
 7     public Node() {}
 8 
 9     public Node(int _val) {
10         val = _val;
11     }
12 
13     public Node(int _val, List _children) {
14         val = _val;
15         children = _children;
16     }
17 };
18 */
19 
20 class Solution {
21     public List postorder(Node root) {
22         List ret = new ArrayList<>();
23         if(root == null){
24             return ret;
25         }
26         end(root,ret);
27         return ret;
28     }
29     public void end(Node root,List ret){
30         
31         for(Node node : root.children){
32             end(node,ret);
33         }
34         ret.add(root.val);
35     }
36 }

2.使用栈进行模拟

 人生苦短，建议递归

 1 /*
 2 // Definition for a Node.
 3 class Node {
 4     public int val;
 5     public List children;
 6 
 7     public Node() {}
 8 
 9     public Node(int _val) {
10         val = _val;
11     }
12 
13     public Node(int _val, List _children) {
14         val = _val;
15         children = _children;
16     }
17 };
18 */
19 
20 class Solution {
21     public List postorder(Node root) {
22         List res = new ArrayList();
23         if (root == null) {
24             return res;
25         }
26         Map map = new HashMap();
27         Deque stack = new ArrayDeque();
28         Node node = root;
29         while(node != null || !stack.isEmpty()){
30             while(node != null){
31                 stack.push(node);
32                 List children = node.children;
33                 if(children != null && children.size() > 0){
34                     map.put(node,0);
35                     node = children.get(0);
36                 }else{
37                     node = null;
38                 }
39             }
40             node = stack.peek();
41             int idx = map.getOrDefault(node , -1) + 1;
42             List children = node.children;
43             if(children != null && children.size() > idx){
44                 map.put(node,idx);
45                 node = children.get(idx);
46                 //stack.push(node);               
47             }else{
48                 res.add(node.val);
49                 stack.pop();
50                 map.remove(node);
51                 node = null;
52             }
53         }
54         return res;
55     }
56 }

还是建议递归