刷题
刷题
learn
learn
日期
Sep 1, 2024
- 用栈实现二叉树先序遍历
- 只要栈不为空，弹出一个节点并访问；
- 然后先压右节点，再压左节点（如果不为空）；
- 用栈实现二叉树中序遍历
- 左子树重复进栈（不往右），直到全部进栈；
- 栈顶弹出一个元素并访问，然后来到右子树，重复1；
- 终止条件：没有子树且栈空
- 用两个栈实现二叉树后序遍历，好写但是不推荐，因为需要收集所有节点，最后逆序弹出，额外空间复杂度
- 用一个栈实现二叉树后序遍历
- 遍历二叉树复杂度分析：
- 时间复杂度，递归和非递归都是每个节点遇到有限几次，当然
- 额外空间复杂度，递归和非递归都需要二叉树高度的空间来保存路径，方便回到上级去
- 存在时间复杂度，额外空间复杂度的遍历方式：
Morris遍历