N 叉树邮购遍历

编程并不是一个机械性的工作，而是需要有思考，有创新的工作，语法是固定的，但解决问题的思路则是依靠人的思维，这就需要我们坚持学习和更新自己的知识。今天golang学习网就整理分享《N 叉树邮购遍历》，文章讲解的知识点主要包括，如果你对文章方面的知识点感兴趣，就不要错过golang学习网，在这可以对大家的知识积累有所帮助，助力开发能力的提升。

590。 n 叉树后序遍历

难度：简单

主题： 堆栈、树、深度优先搜索

给定n叉树的根，返回其节点值的后序遍历.

nary-tree 输入序列化以其级别顺序遍历来表示。每组孩子都由空值分隔（参见示例）

示例1：

• 输入： root = [1,null,3,2,4,null,5,6]
• 输出： [5,6,3,2,4,1]

示例2：

• 输入： root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13 ,空,空,14]
• 输出： [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

限制：

• 树中节点的数量在 [0, 100⁴] 范围内。
• -100 <= node.val <= 100⁴
• n叉树的高度小于等于1000。

后续： 递归解决方案很简单，你能迭代地完成吗？

解决方案：

我们可以递归和迭代地处理它。由于后续要求迭代解决方案，我们将重点关注这一点。后序遍历是指先访问子节点，再访问父节点。

让我们用 php 实现这个解决方案：590。 n 叉树后序遍历

<?php
//Definition for a Node.
class Node {
    public $val = null;
    public $children = [];

    public function __construct($val) {
        $this->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]
?>

解释：

1. 初始化:

   • 创建一个堆栈并将根节点压入其中。
   • 创建一个空数组结果来存储最终的后序遍历。

2. 穿越:

   • 从堆栈中弹出节点，将其值插入到结果数组的开头。
   • 将其所有子项推入堆栈。
   • 继续直到堆栈为空。

3. 结果：

   • 循环结束后，结果数组将包含后序的节点。

这种迭代方法通过使用堆栈并反转通常通过递归完成的过程来有效地模拟后序遍历。

联系链接

如果您发现本系列有帮助，请考虑在 github 上给存储库 一颗星，或在您最喜欢的社交网络上分享该帖子?。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• github

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《N 叉树邮购遍历》文章吧，也可关注golang学习网公众号了解相关技术文章。