首页 > 其他 > 详细

LeetCode 590. N-ary Tree Postorder Traversal

时间:2019-11-27 12:00:21      阅读:59      评论:0      收藏:0      [点我收藏+]

原题链接在这里:https://leetcode.com/problems/n-ary-tree-postorder-traversal/

题目:

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

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

Follow up:

Recursive solution is trivial, could you do it iteratively?

Example 1:

技术分享图片

Input: root = [1,null,3,2,4,null,5,6]
Output: [5,6,3,2,4,1]

Example 2:

技术分享图片

Input: root = [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]
Output: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

Constraints:

  • The height of the n-ary tree is less than or equal to 1000
  • The total number of nodes is between [0, 10^4]

题解:

First add root to stack.

When popping up the top node in stack, add its value into res.

For each of its children. Add them to stack from left to right.

Eventually reverse the res.

Time Complexity: O(V+E).

Space: O(V).

AC Java:

 1 /*
 2 // Definition for a Node.
 3 class Node {
 4     public int val;
 5     public List<Node> children;
 6 
 7     public Node() {}
 8 
 9     public Node(int _val) {
10         val = _val;
11     }
12 
13     public Node(int _val, List<Node> _children) {
14         val = _val;
15         children = _children;
16     }
17 };
18 */
19 class Solution {
20     public List<Integer> postorder(Node root) {
21         List<Integer> res = new ArrayList<>();
22         if(root == null){
23             return res;
24         }
25         
26         Stack<Node> stk = new Stack<>();
27         stk.push(root);
28         while(!stk.isEmpty()){
29             Node cur = stk.pop();
30             res.add(cur.val);
31             
32             for(Node child : cur.children){
33                 stk.push(child);    
34             }
35         }
36         
37         Collections.reverse(res);
38         return res;
39     }
40 }

类似N-ary Tree Preorder TraversalBinary Tree Postorder Traversal.

LeetCode 590. N-ary Tree Postorder Traversal

原文:https://www.cnblogs.com/Dylan-Java-NYC/p/11940478.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!