二叉树采用二叉链表存储结构,要求既不用递归也不用栈,返回二叉树后序遍历序列中第一个结点的指针。
时间: 2024-01-23 21:15:38 浏览: 84
erchashubianli.rar_用二叉链表 进行 二叉树 遍历
可以使用Morris遍历算法实现不用递归也不用栈的二叉树后序遍历。
具体步骤如下:
1. 初始化当前节点为根节点root。
2. 如果当前节点的右子节点为空,说明当前节点已经没有右子树,可以访问当前节点。将当前节点的指针指向左子节点。
3. 如果当前节点的右子节点不为空,找到当前节点的右子树的最左子节点,即当前节点右子树的中序遍历的第一个节点,记为mostRight。
a. 如果mostRight的左指针指向空,说明mostRight还没有被访问过,将mostRight的左指针指向当前节点,并将当前节点的指针指向右子节点,继续遍历。
b. 如果mostRight的左指针指向当前节点,说明mostRight已经被访问过了,可以访问当前节点。将mostRight的左指针重新指向空,并将当前节点的指针指向左子节点。
4. 重复步骤2和3,直到当前节点为空。
代码如下:
```python
def postorderTraversal(root):
if not root:
return None
res = None
cur = root
while cur:
if not cur.right:
res = cur if not res else res
cur = cur.left
else:
mostRight = cur.right
while mostRight.left and mostRight.left != cur:
mostRight = mostRight.left
if not mostRight.left:
mostRight.left = cur
cur = cur.right
else:
mostRight.left = None
res = cur if not res else res
cur = cur.left
return res
```
注意:由于后序遍历是左->右->根,所以在遍历完成一个节点后,需要将其加入到结果序列的头部,而不是尾部。
阅读全文