LeetCode - Easy - 590. N-ary Tree Postorder Traversal

墨蓝 2022-10-06 01:57 110阅读 0赞

## Topic ##

*  Tree

## Description ##

[https://leetcode.com/problems/n-ary-tree-postorder-traversal/][https_leetcode.com_problems_n-ary-tree-postorder-traversal]

Given the root of 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)

**Example 1:**

![042aa242e9be82786f7906e8d95631bb.png][]

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

**Example 2:**

![481a463e68315c2a1a14ec0d9522c4dd.png][]

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 number of nodes in the tree is in the range  \[ 0 , 1 0 4 \] \[0, 10^4\] \[0,104\].
 *   0 < = N o d e . v a l < = 1 0 4 0 <= Node.val <= 10^4 0<=Node.val<=104
 *  The height of the n-ary tree is less than or equal to `1000`.

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

## Analysis ##

方法一：递归版

方法二：迭代法，N叉树后序迭代遍历可以看作N叉树前序**逆**迭代遍历。

## Submission ##

import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    
    import com.lun.util.NAryTree.Node;
    
    public class NAryTreePostorderTraversal { 
    	
    	//方法一：递归法
        public List<Integer> postorder(Node root) { 
            List<Integer> result = new ArrayList<>();
            postorder(root, result);
            return result;
        }
        
        private void postorder(Node root, List<Integer> result) { 
        	if(root == null) return;
        	
        	if(root.children != null) { 
        		for(Node node : root.children) { 
        			postorder(node, result);
        		}
        	}
        	result.add(root.val);
        }
        
        //方法二：迭代法
        public List<Integer> postorder2(Node root) { 
        	List<Integer> result = new LinkedList<>();
        	if(root == null)
        		return result;
        	LinkedList<Node> stack = new LinkedList<>();
        	stack.push(root);
        	while(!stack.isEmpty()) { 
        		Node node = stack.pop();
        		result.add(0, node.val);
        		
        		if(node.children != null)
        			for(Node n : node.children) 
        				stack.push(n);
        		
        	}
        	return result;
        }
    }

## Test ##

import static org.junit.Assert.*;
    
    import org.hamcrest.collection.IsIterableContainingInOrder;
    import org.junit.Test;
    
    import com.lun.util.NAryTree;
    
    public class NAryTreePostorderTraversalTest { 
    
    	@Test
    	public void test() { 
    		NAryTreePostorderTraversal obj = new NAryTreePostorderTraversal();
    
    		assertThat(obj.postorder(NAryTree.integersToNAryTree(1,null,3,2,4,null,5,6)),//
    				IsIterableContainingInOrder.contains(5, 6 ,3, 2, 4, 1));
    		assertThat(obj.postorder(NAryTree.integersToNAryTree(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)),//
    				IsIterableContainingInOrder.contains(2, 6, 14, 11, 7, 3, 12, 8, 4, 13, 9, 10, 5, 1));
    	}
    	@Test
    	public void test2() { 
    		NAryTreePostorderTraversal obj = new NAryTreePostorderTraversal();
    		
    		assertThat(obj.postorder2(NAryTree.integersToNAryTree(1,null,3,2,4,null,5,6)),//
    				IsIterableContainingInOrder.contains(5, 6 ,3, 2, 4, 1));
    		assertThat(obj.postorder2(NAryTree.integersToNAryTree(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)),//
    				IsIterableContainingInOrder.contains(2, 6, 14, 11, 7, 3, 12, 8, 4, 13, 9, 10, 5, 1));
    	}
    }

[https_leetcode.com_problems_n-ary-tree-postorder-traversal]: https://leetcode.com/problems/n-ary-tree-postorder-traversal/
[042aa242e9be82786f7906e8d95631bb.png]: /images/20221005/b329c40f1f8c4cbc957f61f5eb31bbfc.png
[481a463e68315c2a1a14ec0d9522c4dd.png]: /images/20221005/0d6ed9dda95841f1a1c92ba184c4e216.png