问题标签 [postorder]

我一直在研究算法和数据结构，并且我为二叉树编写了一个后序遍历，没有使用递归并且只使用一个堆栈。

这是代码：

这段代码确实有效，但我花了很长时间才想出它。

有人可以解释一下思考这个问题的直观方式是什么吗？

我希望能够使用逻辑来重现它，而不是像我在它上面花费的时间一样多。

我正在尝试构建一个完整的二叉树（完全意味着每个非叶节点都有两个叶节点连接到它，即node->right和node->left是!= NULL）只给定树的后序遍历。另外，给出后序遍历中的节点是否为叶节点。给定的后序遍历如下所示：

例如，格式中的一行"%d(%le)"是叶节点并且"(%le %le)"是非叶节点。通常你不能只使用后序来构建树，因为连接会有多种可能性，但我确信能够区分叶子节点和非叶子节点在某种程度上很重要。我当前的功能如下所示：

其中index等于树中的节点数 - 1。显然，此实现仅在右侧构建节点。如何更新它以正确构建树？

编辑：让我添加一些关于我所知道的更多信息。所以，第一个节点总是必须是叶节点，最后一个节点总是必须是根节点。由于这不是二叉搜索树，而是简单的二叉树，因此您不能每次都使用更新的范围参数递归调用该函数。我的实现应该在 O(n) 时间内解决它，但我只是不知道如何在构建树时利用节点是否为叶节点的知识。

所以现在我实现了顺序遍历，我需要打印节点所在位置的深度。所以如果我的树是这样的：

然后当它打印 3 时，它的深度应该是 2。如果我递归调用它，我将在哪里增加深度。如果我要上树，我将如何减少它？

我的代码是

我要问的是我会在哪里增加级别以显示节点的适当深度，为什么？

我正在研究一个著名的问题，称为二叉树的直径。我知道这已经讨论了很多次（二叉树的直径），但解释似乎不正确。特别是，单个节点树应该返回 0，而不是 1（我从 Leetcode 自己的检查器中检查过）。无论如何，这是问题陈述：

给定一棵二叉树，您需要计算树的直径长度。二叉树的直径是树中任意两个节点之间最长路径的长度。此路径可能会或可能不会通过根。

答案分别是 0、1 和 5。乍一看，似乎计算左子树的边数和右子树的数应该得出答案。

所以我从后序递归开始（自下而上）：

到目前为止，一切都很好。但是代码不起作用，我很难理解那里的一些解决方案。例如：

为什么要比较左子树和右子树？为什么+1？还有，有人说找高度，有人说找深度。这令人困惑，我觉得人们只是在抛出术语......任何澄清都是有帮助的。

我对后序遍历有疑问。

网上的代码是：

我不确定这将如何到达打印线。在这里它会一直向左走，直到没有左边，所以我们永远不会过去

当没有剩下这一行时：

不会满足，也不会打印。

该程序的目标是创建一个名为 Product 的对象并将该产品对象添加到树对象中。一旦添加了六七个产品，主函数需要调用析构函数（.~BinarySearchTree()），通过实现后订单删除函数来删除所有产品。当我运行程序时，它会引发异常（读取访问冲突）。~BinarySearchTree() 和 postOrderDeletion 的实现在 BinarySearchTree.cpp

我尝试通过实施常规方法来删除产品，但这没有用。我尝试一个一个删除产品：它工作，但程序需要实现一个后订单删除方法。

骄傲的.h

产品.cpp

节点.h

BinarySearchTree.h

二进制搜索树.cpp

主文件

我正在解决这个问题 - Find PostOrder traversal from Inorder and Preorder traversals of a binary tree。在 GeeksForGeeks 上，我看到了以下解决方案：

现在，我知道在后序中，我们在遍历左右子树后访问该节点，这就是为什么，我可以从 printPostOrder() 方法中的注释推断出首先对左子树进行处理，然后是右子树，然后是节点的正在打印数据。我在纸上画了一些初始的递归调用，它工作正常，但我就是不明白有人怎么能想出这个解决方案？我在为右子树调用 printPostOrder 的语句中特别困惑。谁能帮我理解递归背后的逻辑是什么，以及如何通过正确地可视化它来理解它？

我尝试使用全局数组来保存值。但是我如何编写递归的基本情况？如果我每次都返回一个数组，如何保持树遍历的正确顺序？

我有一个选定的数组

和带有孩子的树结构：

如果 node.Id + ':' + node.name 与 this.selectedArray 中的任何项目都不匹配，我想从树中删除该节点。

我无法找到一种算法，该算法允许我从深度嵌套的树中删除与 this.selected 中的任何项目不匹配的所有对象数据。

这是代码：

我认为问题在于执行具有 this.slice 的代码后，它会返回并且不会转到其兄弟。对此有何建议？

有什么特殊的方法可以做到这一点？（不是代码方法，就像头部的方法）

例如，这是树的后序：1 4 3 2 5 7 8 9 6 10

我怎么知道如何构建树？

谢谢你。