python-leetcode 35.二叉树的中序遍历

给定一个二叉树的根节点root,返回它的中序遍历。

---

方法一：递归

二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质

运行过程

1. 从根节点 1 开始：

   • 递归遍历左子树：1 的左子树为空，直接返回。

   • 将 1 的值添加到结果列表 res 中：res = [1]。

   • 递归遍历右子树：1 的右子树是 2。

2. 进入节点 2：

   • 递归遍历左子树：2 的左子树是 3。

   • 进入节点 3：

     • 递归遍历左子树：3 的左子树为空，直接返回。

     • 将 3 的值添加到结果列表 res 中：res = [1, 3]。

     • 递归遍历右子树：3 的右子树为空，直接返回。

   • 将 2 的值添加到结果列表 res 中：res = [1, 3, 2]。

   • 递归遍历右子树：2 的右子树为空，直接返回。

3. 遍历结束，返回结果 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)