后序非递归算法计算二叉树高度

二叉树高度的非递归算法可以通过层次遍历实现。下面是一种基于队列的算法：

1. 初始化一个空队列，并将根节点入队。
2. 初始化一个变量 height，并将其置为 0。
3. 循环执行以下步骤，直到队列为空：
a. 获取当前队列的长度，表示当前层的节点个数。
b. 遍历当前层的所有节点：
i. 将当前节点出队。
ii. 如果当前节点有左子节点，将其入队。
iii. 如果当前节点有右子节点，将其入队。
c. 增加 height 的值。
4. 返回 height 的值作为二叉树的高度。

这种非递归算法利用了队列的先进先出特性，每层的节点按照从左到右的顺序依次入队，从而实现了按层遍历。通过记录遍历的层数，最终得到二叉树的高度。

相关问题

先序非递归遍历算法遍历二叉树 ​中序非递归遍历算法遍历二叉树 ​后序非递归遍历算法遍历二叉树 ​层序遍历二叉树

好的，我可以给您介绍一下二叉树的四种非递归遍历算法以及层序遍历。

先序非递归遍历算法：
1. 新建一个栈，将根节点入栈。
2. 当栈不为空时，取出栈顶元素并访问它。
3. 将当前节点的右子节点（如果存在）入栈，再将左子节点（如果存在）入栈。
4. 重复步骤2-3，直到栈为空。

中序非递归遍历算法：
1. 新建一个栈，将根节点入栈。
2. 如果当前节点不为空，则将当前节点的左子节点全部入栈，并将当前节点置为左子节点。
3. 如果当前节点为空，则取出栈顶元素并访问它，将当前节点置为它的右子节点。
4. 重复步骤2-3，直到栈为空。

后序非递归遍历算法：
1. 新建两个栈：s1和s2，将根节点入s1。
2. 当s1不为空时，取出栈顶元素并将其压入s2中。
3. 将当前节点的左子节点（如果存在）入s1，再将右子节点（如果存在）入s1。
4. 重复步骤2-3，直到s1为空。
5. 依次访问s2中的元素即可得到后序遍历结果。

层序遍历算法：
1. 新建一个队列，将根节点入队。
2. 当队列不为空时，取出队首元素并访问它。
3. 将当前节点的左子节点（如果存在）入队，再将右子节点（如果存在）入队。
4. 重复步骤2-3，直到队列为空。

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

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

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