. N-ary Tree Mail Order Traverse-PHP Tutorial-php.cn

590. N-ary Tree Postorder Traversa

Difficulty:Easy

Topics:Stack, Tree, Depth-First Search

Given the root of an n-ary tree, returnthe 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:

. N-ary Tree Postorder Traversa

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

Example 2:

. N-ary Tree Postorder Traversa

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 the nodes in the tree is in the range [0, 100⁴].
-100 <= Node.val <= 100⁴
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?

Solution:

We can approach it both recursively and iteratively. Since the follow-up asks for an iterative solution, we'll focus on that. Postorder traversal means visiting the children nodes first and then the parent node.

Let's implement this solution in PHP:590. N-ary Tree Postorder Traversal

        val = $val; } } /** * @param Node $root * @return integer[] */ function postorder($root) { ... ... ... /** * go to ./solution.php */ } // Example 1: $root1 = new Node(1); $root1->children = [ $node3 = new Node(3), new Node(2), new Node(4) ]; $node3->children = [ new Node(5), new Node(6) ]; print_r(postorder($root1)); // Output: [5, 6, 3, 2, 4, 1] // Example 2: $root2 = new Node(1); $root2->children = [ new Node(2), $node3 = new Node(3), $node4 = new Node(4), $node5 = new Node(5) ]; $node3->children = [ $node6 = new Node(6), $node7 = new Node(7) ]; $node4->children = [ $node8 = new Node(8) ]; $node5->children = [ $node9 = new Node(9), $node10 = new Node(10) ]; $node7->children = [ new Node(11) ]; $node8->children = [ new Node(12) ]; $node9->children = [ new Node(13) ]; $node11 = $node7->children[0]; $node11->children = [ new Node(14) ]; print_r(postorder($root2)); // Output: [2, 6, 14, 11, 7, 3, 12, 8, 4, 13, 9, 10, 5, 1] ?>Explanation:
        
         Initialization:
          
           Create a stack and push the root node onto it.
           Create an empty array result to store the final postorder traversal.
          
         Traversal:
          
           Pop the node from the stack, insert its value at the beginning of the result array.
           Push all its children onto the stack.
           Continue until the stack is empty.
          
         Result:
          
           The result array will contain the nodes in postorder after the loop finishes.
          
        
This iterative approach effectively simulates the postorder traversal by using a stack and reversing the process typically done by recursion.
Contact Links
If you found this series helpful, please consider giving therepositorya star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
        
         LinkedIn
         GitHub
        
The above is the detailed content of . N-ary Tree Mail Order Traverse. For more information, please follow other related articles on the PHP Chinese website!