python-leetcode 35.二叉树的中序遍历
给定一个二叉树的根节点root,返回它的中序遍历。
方法一：递归
二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质
运行过程
-
从根节点
1开始：-
递归遍历左子树：
1的左子树为空，直接返回。 -
将
1的值添加到结果列表res中：res = [1]。 -
递归遍历右子树：
1的右子树是2。
-
-
进入节点
2：-
递归遍历左子树：
2的左子树是3。 -
进入节点
3：-
递归遍历左子树：
3的左子树为空，直接返回。 -
将
3的值添加到结果列表res中：res = [1, 3]。 -
递归遍历右子树：
3的右子树为空，直接返回。
-
-
将
2的值添加到结果列表res中：res = [1, 3, 2]。 -
递归遍历右子树：
2的右子树为空，直接返回。
-
-
遍历结束，返回结果
res = [1, 3, 2]
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: Optional[TreeNode]
:rtype: List[int]
"""
res=[] #存储遍历结果
self.inorder(root,res) #中序遍历
return res
def inorder(self,root,res): #递归函数，用于实现中序遍历
if not root: #如果当前节点 root 为空，直接返回
return
self.inorder(root.left,res)
res.append(root.val) #将当前节点的值 root.val 添加到结果列表 res 中
self.inorder(root.right,res)
时间复杂度：O(n)n为二叉树节点的个数
空间复杂度：O(n)
方法二：迭代
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: Optional[TreeNode]
:rtype: List[int]
"""
res=[] #空列表用于存储遍历结果
stack=[] #空列表用作栈来辅助遍历
while root or stack: #当 root 不为空或栈 stk 不为空时，继续循环
while root: #当root不为空时，将root推入栈stk中
stack.append(root) #将 root 移动到其左子节点
root=root.left #将当前节点的所有左子节点推入栈中，直到到达最左侧的节点
root=stack.pop() #从栈 stk 中弹出栈顶节点，赋值给 root,当前子树的最左侧节点
res.append(root.val) #将当前节点 root 的值 root.val 添加到结果列表 res 中
root=root.right #将 root 移动到其右子节点
return res
时间复杂度：O(n)
空间复杂度：O(n)
方法三：Morris中序遍历
Morris 遍历算法是另一种遍历二叉树的方法，它能将非递归的中序遍历空间复杂度降为O(1)。
Morris 遍历算法整体步骤如下（假设当前遍历到的节点为x）：
1.如果x无左孩子，先将x的值加入答案数组，再访问x的右孩子，即x=x.right
2.如果x有左孩子，则找到x左子树上最右的节点（即左子树中序遍历的最后一个节点x,x在中序遍历中的前驱节点），记为predecessor。根据predecessor的右孩子是否为空，进行如下操作:
如果predecessor的右孩子为空，则将其右孩子指向x，然后访问x的左孩子，即x=x.left。
如果predecessor的右孩子不为空，则此时其右孩子指向x，说明已经遍历完x的左子树，将predecessor的右孩子置空，将x的值加入答案数组，然后访问x的右孩子，即x=x.right。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: Optional[TreeNode]
:rtype: List[int]
"""
res=[] #列表，用来存储最终的中序遍历结果
predcessor=None #当前节点的前驱节点（即，当前节点的左子树中最右边的节点）
while root: #只要当前节点不为空，就继续遍历
if root.left:
predcessor=root.left #predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
while predcessor.right and predcessor.right != root:
predcessor=predcessor.right
if predcessor.right is None: #predecessor 的右指针指向 root，继续遍历左子树
predcessor.right=root #前驱节点的右子树为空，把它的右子树指向当前节点 root
root=root.left #移动到它的左子树，继续遍历
else:#前驱节点的右子树指向了当前节点，说明左子树遍历完成，可以访问当前节点
res.append(root.val)
predcessor.right=None
root=root.right
else:#当前节点没有左子树，直接访问当前节点，并将 root 移动到右子树
res.append(root.val)
root=root.right
return res
时间复杂度：O(n)
空间复杂度：O(1)