Welcome to Subscribe On Youtube

590. N-ary Tree Postorder Traversal

Description

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:

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 number of nodes in the tree is in the range [0, 104].
• 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?

Solutions

• Java
• C++
• Python
• Go
• TypeScript

• /*
  // Definition for a Node.
  class Node {
      public int val;
      public List<Node> children;
  
      public Node() {}
  
      public Node(int _val) {
          val = _val;
      }
  
      public Node(int _val, List<Node> _children) {
          val = _val;
          children = _children;
      }
  };
  */
  
  class Solution {
      public List<Integer> postorder(Node root) {
          LinkedList<Integer> ans = new LinkedList<>();
          if (root == null) {
              return ans;
          }
          Deque<Node> stk = new ArrayDeque<>();
          stk.offer(root);
          while (!stk.isEmpty()) {
              root = stk.pollLast();
              ans.addFirst(root.val);
              for (Node child : root.children) {
                  stk.offer(child);
              }
          }
          return ans;
      }
  }
  

• /*
  // Definition for a Node.
  class Node {
  public:
      int val;
      vector<Node*> children;
  
      Node() {}
  
      Node(int _val) {
          val = _val;
      }
  
      Node(int _val, vector<Node*> _children) {
          val = _val;
          children = _children;
      }
  };
  */
  
  class Solution {
  public:
      vector<int> postorder(Node* root) {
          vector<int> ans;
          if (!root) return ans;
          stack<Node*> stk{ {root} };
          while (!stk.empty()) {
              root = stk.top();
              ans.push_back(root->val);
              stk.pop();
              for (Node* child : root->children) stk.push(child);
          }
          reverse(ans.begin(), ans.end());
          return ans;
      }
  };
  

• """
  # Definition for a Node.
  class Node:
      def __init__(self, val=None, children=None):
          self.val = val
          self.children = children
  """
  
  
  class Solution:
      def postorder(self, root: 'Node') -> List[int]:
          ans = []
          if root is None:
              return ans
          stk = [root]
          while stk:
              node = stk.pop()
              ans.append(node.val)
              for child in node.children:
                  stk.append(child)
          return ans[::-1]
  
  

• /**
   * Definition for a Node.
   * type Node struct {
   *     Val int
   *     Children []*Node
   * }
   */
  
  func postorder(root *Node) []int {
  	var ans []int
  	if root == nil {
  		return ans
  	}
  	stk := []*Node{root}
  	for len(stk) > 0 {
  		root = stk[len(stk)-1]
  		stk = stk[:len(stk)-1]
  		ans = append([]int{root.Val}, ans...)
  		for _, child := range root.Children {
  			stk = append(stk, child)
  		}
  	}
  	return ans
  }
  

• /**
   * Definition for node.
   * class Node {
   *     val: number
   *     children: Node[]
   *     constructor(val?: number) {
   *         this.val = (val===undefined ? 0 : val)
   *         this.children = []
   *     }
   * }
   */
  
  function postorder(root: Node | null): number[] {
      const res = [];
      const dfs = (root: Node | null) => {
          if (root == null) {
              return;
          }
          for (const node of root.children) {
              dfs(node);
          }
          res.push(root.val);
      };
      dfs(root);
      return res;
  }
  
  

All Problems

All Solutions