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

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

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是二叉树的节点数。

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

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

1. 定义一个栈和一个指针p，初始时p指向根节点，栈为空。
2. 循环执行以下操作，直到栈为空：
a. 将p指向的节点及其左子树依次入栈，直到p指向的节点没有左子树。
b. 循环执行以下操作，直到栈顶元素的右子树为空或者栈顶元素的右子树已经被访问过：
i. 将栈顶元素出栈，并将其右子树标记为已访问。
ii. 如果栈顶元素的右子树为空，或者栈顶元素的右子树已经被访问过，就输出栈顶元素。
c. 如果栈不为空，将栈顶元素的右子树标记为未访问，并将p指向栈顶元素的右子树。

具体的C语言代码如下：

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

void postorderTraversal(TreeNode* root) {
    if (!root) {
        return;
    }
    TreeNode* stack[100];
    int top = -1;
    TreeNode* p = root;
    TreeNode* pre = NULL;
    while (p || top != -1) {
        while (p) {
            stack[++top] = p;
            p = p->left;
        }
        p = stack[top];
        if (p->right == NULL || p->right == pre) {
            printf("%d ", p->val);
            pre = p;
            top--;
            p = NULL;
        } else {
            p = p->right;
        }
    }
}

其中，top表示栈顶指针，pre表示已经访问过的右子树的指针。具体实现中，我们使用一个数组来模拟栈，数组的大小可以根据实际情况进行修改。