树-94. 二叉树的中序遍历-PYTHON
程序员文章站
2024-01-11 16:02:10
...
迭代
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = list()
stack = list()
while stack or root:
if root:
stack.append(root)
root = root.left #因为是中序遍历,所以一直向左走一直走到没有左孩子为止
else:
tmp = stack.pop() #当没有左孩子了,将当前节点的值放入返回序列中
res.append(tmp.val)
root = tmp.right #查看当前节点是否有右孩子
return res
递归
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = list()
def zhong(root):
if not root:
return
zhong(root.left)
res.append(root.val)
zhong(root.right)
zhong(root)
return res
莫里斯遍历
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = list()
pre = None
while root:
# 如果当前节点的左节点不为空就把当前节点连带右节点全部挂到左节点上
if root.left:
pre = root.left
while pre.right:
pre = pre.right #找到锁定节点左孩子的最右孩子,用于连接
pre.right = root
tmp = root
root = root.left
tmp.left = None #去除线索指向
#如果不存在左子树了,就打印当前节点,向右遍历
else:
res.append(root.val)
root = root.right
return res
上一篇: JAVA常见面试题总结