二叉树后序遍历的非递归算法

二叉树后序遍历的非递归算法可以使用两个栈来实现：

1. 定义两个栈s1和s2，将根节点压入s1中。
2. 当s1不为空时，弹出栈顶节点，将其压入s2中。
3. 如果该节点有左子节点，将左子节点压入s1中。
4. 如果该节点有右子节点，将右子节点压入s1中。
5. 重复步骤2-4直到s1为空。
6. 依次弹出s2中的节点，即为后序遍历结果。

以下是该算法的Python代码实现：

def postorderTraversal(root):
    if not root:
        return []
    s1, s2, res = [root], [], []
    while s1:
        node = s1.pop()
        s2.append(node)
        if node.left:
            s1.append(node.left)
        if node.right:
            s1.append(node.right)
    while s2:
        res.append(s2.pop().val)
    return res

该算法的时间复杂度为O(n)，空间复杂度为O(n)。

相关问题

二叉树后序遍历非递归算法

二叉树后序遍历的非递归算法可以使用两个栈来实现。具体步骤如下：

1. 定义两个栈stack1和stack2，用于存放节点。
2. 将根节点压入stack1中。
3. 循环执行以下操作，直到stack1为空：
1. 从stack1中弹出一个节点p，并将其压入stack2中。
2. 将p的左子节点压入stack1中。
3. 将p的右子节点压入stack1中。
4. 循环执行以下操作，直到stack2为空：
1. 从stack2中弹出一个节点p，并输出p的值。

这种算法的思路是，先按照根节点、右子节点、左子节点的顺序遍历二叉树，并将遍历的结果压入stack2中。最后从stack2中依次弹出节点，得到的就是后序遍历的结果。

下面是使用Python代码实现的示例：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def postorderTraversal(root: TreeNode) -> List[int]:
    if not root:
        return []
    stack1, stack2 = [root], []
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    res = []
    while stack2:
        res.append(stack2.pop().val)
    return res

这个算法的时间复杂度和空间复杂度都是O(n)，其中n是二叉树的节点数。

编写实现采用二叉链表作为存储结构的二叉树后序遍历非递归算法。

### 回答1：
二叉树后序遍历的非递归算法可以使用二叉链表作为存储结构来实现。具体实现方法如下：

1. 定义一个栈，用于存储遍历过程中的节点。

2. 从根节点开始，将根节点入栈。

3. 循环执行以下步骤，直到栈为空：

a. 取出栈顶节点，如果该节点没有左右子节点或者其左右子节点已经被访问过，则输出该节点的值，并将其出栈。

b. 否则，将该节点的右子节点和左子节点依次入栈。

4. 遍历结束。

需要注意的是，在访问一个节点之前，需要先判断其左右子节点是否已经被访问过，以避免重复访问。另外，由于后序遍历的顺序是左右根，所以在入栈时需要先将右子节点入栈，再将左子节点入栈，以保证出栈顺序的正确性。

### 回答2：
二叉树的后序遍历可以采用非递归算法实现，使用栈作为辅助结构。具体步骤如下：

1.将根节点入栈，如果栈为空则遍历结束，否则执行步骤2。

2.取出栈顶元素，如果该元素为叶子节点或者其左右子树已经遍历完毕，则输出该节点的值，并将其弹出。否则，将该节点再次入栈，先将右子树入栈，再将左子树入栈。这样可以保证左子树会先于右子树被遍历。

3.重复执行步骤2，直到栈为空。

采用二叉链表作为存储结构的二叉树后序遍历非递归算法的实现，需要定义一个栈结构StackNode来辅助遍历。栈中存储的是二叉树的结点指针。

具体实现过程如下：

typedef struct StackNode{
    BiTNode *p;  //指向二叉树结点的指针
    int     flag;   //标记是否访问过
}StackNode;

void PostOrder(BiTNode *root) {
    if(!root) {
        return;
    }

    StackNode stack[MAXSIZE];   //定义一个栈结构
    int top = -1;
    BiTNode *p = root;

    while(p || top != -1) {
        while(p) {    //先将左子树全部入栈
            StackNode node = { p, 0 };
            stack[++top] = node;
            p = p->lchild;
        }

        StackNode node = stack[top];  //查看栈顶元素
        if(node.flag == 1) {      //如果栈顶元素已经访问过
            printf("%d ", node.p->data);    //输出该结点的值
            top--;
        }
        else {
            node.flag = 1;   //标记该节点已被访问
            stack[top] = node;

            p = node.p->rchild;   //查看该结点的右子树
        }
    }
}

这段代码中，先将二叉树的根节点入栈，然后遍历左子树，直到遇到叶子结点。当遇到叶子结点时，从栈中取出该节点，查看是否已经访问过。如果已经访问过，则输出该节点的值，并弹出它；如果没有访问过，则将它的标记位设为1，再将它入栈，查看右子树。如果右子树为空，则弹出该节点。这个算法的时间复杂度为O(n)，空间复杂度为O(n)。

### 回答3：
二叉树是计算机科学中非常重要的数据结构之一，它有多种遍历方式，其中后序遍历是指先访问该结点的左子树，再访问该结点的右子树，最后访问该结点本身。采用二叉链表作为存储结构的二叉树后序遍历非递归算法可以通过栈来实现。

具体实现方法如下：

1. 首先将根节点入栈，并将左子树依次入栈。
2. 当栈顶结点无左子树或者左子树已被访问时，判断是否存在右子树。
3. 如果存在右子树，则将右子树入栈，并重复第一步操作，直到栈为空或所有结点都已被访问。

具体的代码实现如下：

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<int> postorderTraversal(TreeNode* root) {
  stack<TreeNode*> s;
  vector<int> result;
  if (!root) return result;
  s.push(root);
  while (!s.empty()) {
    TreeNode* node = s.top();
    if (!node->left && !node->right) {
      result.push_back(node->val);
      s.pop();
    } else {
      if (node->right) s.push(node->right);
      if (node->left) s.push(node->left);
      node->left = node->right = NULL;
    }
  }
  return result;
}

该算法的时间复杂度为 O(n)，空间复杂度为 O(log n)（最坏情况下为 O(n)）。其中，n 表示树中结点数目。通过采用非递归实现方式，该算法能够有效地避免栈溢出的问题，同时提高遍历效率。