二阶树的发布顺序遍历而不递归

Question

在不使用递归的情况下,对二叉树进行后序遍历的算法是什么？

Answer 1

这是具有一个堆栈且没有访问标志的版本:

private void postorder(Node head) {
  if (head == null) {
    return;
  }
  LinkedList<Node> stack = new LinkedList<Node>();
  stack.push(head);

  while (!stack.isEmpty()) {
    Node next = stack.peek();

    boolean finishedSubtrees = (next.right == head || next.left == head);
    boolean isLeaf = (next.left == null && next.right == null);
    if (finishedSubtrees || isLeaf) {
      stack.pop();
      System.out.println(next.value);
      head = next;
    }
    else {
      if (next.right != null) {
        stack.push(next.right);
      }
      if (next.left != null) {
        stack.push(next.left);
      }
    }
  }
}

Answer 2

Here's a link which provides two other solutions without using any visited flags.

https://leetcode.com/problems/binary-tree-postorder-traversal/

This is obviously a stack-based solution due to the lack of parent pointer in the tree. (We wouldn't need a stack if there's parent pointer).

We would push the root node to the stack first. While the stack is not empty, we keep pushing the left child of the node from top of stack. If the left child does not exist, we push its right child. If it's a leaf node, we process the node and pop it off the stack.

We also use a variable to keep track of a previously-traversed node. The purpose is to determine if the traversal is descending/ascending the tree, and we can also know if it ascend from the left/right.

If we ascend the tree from the left, we wouldn't want to push its left child again to the stack and should continue ascend down the tree if its right child exists. If we ascend the tree from the right, we should process it and pop it off the stack.

We would process the node and pop it off the stack in these 3 cases:

1. The node is a leaf node (no children)
2. 我们只是从左边遍历树,没有正确的孩子.
3. 我们只是从右边遍历树.

Answer 3

以下是维基百科的示例:

nonRecursivePostorder(rootNode)
  nodeStack.push(rootNode)
  while (! nodeStack.empty())
    currNode = nodeStack.peek()
    if ((currNode.left != null) and (currNode.left.visited == false))
      nodeStack.push(currNode.left)
    else 
      if ((currNode.right != null) and (currNode.right.visited == false))
        nodeStack.push(currNode.right)
      else
        print currNode.value
        currNode.visited := true
        nodeStack.pop()

Answer 4

这是我用于迭代、后序遍历的方法。我喜欢这种方法，因为：

1. 它只处理每个循环周期的单个转换，因此很容易遵循。
2. 类似的解决方案适用于中序和预序遍历

代码：

enum State {LEFT, RIGHT, UP, CURR}

public void iterativePostOrder(Node root) {
  Deque<Node> parents = new ArrayDeque<>();
  Node   curr = root;
  State state = State.LEFT;

  while(!(curr == root && state == State.UP)) {
    switch(state) {
      case LEFT:
        if(curr.left != null) {
          parents.push(curr);
          curr = curr.left;
        } else {
          state = RIGHT;
        }
        break;
      case RIGHT:
        if(curr.right != null) {
          parents.push(curr);
          curr = curr.right;
          state = LEFT;
        } else {
          state = CURR;
        }
        break; 
      case CURR:
        System.out.println(curr);
        state = UP;
        break;
      case UP: 
        Node child = curr;
        curr = parents.pop();
        state = child == curr.left ? RIGHT : CURR;
        break;
      default:
        throw new IllegalStateException();
    }
  }
}

解释：

你可以考虑这样的步骤：

1. 尝试左
   • 如果存在左节点：再次尝试 LEFT
   • 如果左节点不存在：尝试 RIGHT
2. 尝试正确
   • 如果存在正确的节点：从那里尝试 LEFT
   • 如果不存在任何权利，则您处于困境：尝试 CURR
3. 试试电流
   • 打印当前节点
   • 以下所有节点均已执行（后序）：Try UP
4. 试试看
   • 如果节点是root，则没有UP，所以EXIT
   • 如果从左边上来，试试右边
   • 如果从右边过来，试试 CURR