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 resdef 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.rightif predcessor.right is None: #predecessor 的右指针指向 root，继续遍历左子树predcessor.right=root #前驱节点的右子树为空，把它的右子树指向当前节点 rootroot=root.left #移动到它的左子树，继续遍历else:#前驱节点的右子树指向了当前节点，说明左子树遍历完成，可以访问当前节点res.append(root.val)predcessor.right=None root=root.rightelse:#当前节点没有左子树，直接访问当前节点，并将 root 移动到右子树res.append(root.val)root=root.rightreturn res时间复杂度：O(n)
空间复杂度：O(1)