tree - 我可以在没有递归和堆栈的情况下对二叉树进行中序遍历吗？

Question

任何人都可以给我一个在没有递归和不使用堆栈的情况下按顺序遍历二叉树的解决方案吗？

Answer 1

第二次编辑:我认为这是正确的。除了通常的 node.left_child 和 node.right_child 之外，还需要 node.isRoot、node.isLeftChild 和 node.parent。

state = "from_parent"
current_node = root
while (!done)
  switch (state)
    case "from_parent":
      if current_node.left_child.exists
        current_node = current_node.left_child
        state = "from_parent"
      else
        state = "return_from_left_child"
    case "return_from_left_child"
      if current_node.right_child.exists
        current_node = current_node.right_child
        state = "from_parent"
      else
        state = "return_from_right_child"
    case "return_from_right_child"
      if current_node.isRoot
        done = true
      else
        if current_node.isLeftChild
         state = "return_from_left_child"
        else
         state = "return_from_right_child"
        current_node = current_node.parent