我们可以在python的单个代码中编写顺序、前顺序和后顺序吗？不使用递归

Question

我想在O（N）时间复杂度和O（N）空间中，使用单堆栈，不使用递归，以单个代码（前序、后序、内序）对所有二叉树顺序进行编码

有人能帮我吗

Answer 1

您可以使用堆栈，并在每个推送节点上附带订单标识（“pre”、“in”或“post”）。然后，代码可以检查这是否匹配所需的遍历顺序，以决定是否生成节点的值

代码：

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

    def traversal(self, order="pre"):
        stack = [(self, "pre")]
        while stack:
            node, nodeorder = stack.pop()
            if nodeorder == order:
                yield node.value
            if nodeorder == "pre":
                stack.append((node, "in"))
                if node.left:
                    stack.append((node.left, "pre"))
            elif nodeorder == "in":
                stack.append((node, "post"))
                if node.right:
                    stack.append((node.right, "pre"))

所以traversal应该作为第二个参数获取“pre”、“in”或“post”，这取决于您想要的顺序

示例树：

         4
        / \
       2   5
      / \   \
     1   3   7
            /
           6

…和相应的代码：

root = Node(4,
    Node(2,
        Node(1),
        Node(3)
    ),
    Node(5,
        None,
        Node(7,
            Node(6)
        )
    )
)

print(*root.traversal("pre"))   # 4 2 1 3 5 7 6
print(*root.traversal("in"))    # 1 2 3 4 5 6 7
print(*root.traversal("post"))  # 1 3 2 6 7 5 4