【Leetcode】94. Binary Tree Inorder Traversal

2023-12-30 10:37:52

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

文章目录

1. 描述
2. 解决

1. 描述

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

2. 解决

2.1 递归

前序遍历：中 - 左 - 右
中序遍历：左 - 中 - 右
后序遍历：左 - 右 - 中

终止条件： 当前节点为空时
函数内： 递归的调用左节点，打印当前节点，再递归调用右节点
时间复杂度： O(n)
空间复杂度： O(h)，h 是树的高度

# 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: TreeNode
        :rtype: List[int]
        """
        res = []
        def dfs(root):
            if not root:  # 递归出口
                return
            dfs(root.left)  # 左
            res.append(root.val)  # 中
            dfs(root.right)  # 右
        dfs(root)
        return res

2.2 迭代

采用方法： 使用栈（stack）：节点存入stack，节点的值存入res。

中序遍历：左 - 中 - 右

总的来说中序遍历就一句话：入者有左则再入，无左则出；出者有右则入，无右则再出

入栈成为栈顶的元素有左孩子，则左孩子继续入栈，没有左孩子，则栈顶出栈
出栈的元素有右孩子，则右孩子入栈成为栈顶，没有右孩子，则栈顶继续出栈

时间复杂度： O(n)
空间复杂度： O(h)，h是树的高度

# 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: TreeNode
        :rtype: List[int]
        """
        res = []
        stack = []
        while root or stack:  # 迭代出口（or：或门）
            if root:  # 入栈
                stack.append(root)
                root = root.left  # root指向左孩子
            else:  # 出栈
                tmp = stack.pop()  # tmp标记出栈元素
                res.append(tmp.val)  # 出栈元素值写入res
                root = tmp.right  # root指向右孩子
        return res

2.3 莫里斯（Morris）遍历

采用方法： 树→ 链表，无需额外空间。

中序遍历：左 - 中 - 右

如果左节点不为空，就将当前节点连带右子树全部挂到左节点的最右子树下面：

具体步骤：

root.left 不为空：
1. 找到root.left 的最右子节点，该节点.right = root
2. 改变根节点
  
  先备份原根节点：tmp = root
  1. 改变根节点为原根节点的左孩子：root = root.left
  2. 断开原根节点与左孩子的联系：tmp.left = None
root.left 为空：

即，只有右孩子，加入res即可。

时间复杂度： O(n)，其中 n 为二叉搜索树的节点个数。Morris 遍历中每个节点会被访问两次，因此总时间复杂度为 O(2n) = O(n)
空间复杂度： O(1)

# 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: TreeNode
        :rtype: List[int]
        """
        res = []
        while root:
            if root.left:
                # predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
        		predecessor = root.left
        		while predecessor.right:
            		predecessor = predecessor.right
        
        		# 让 predecessor 的右指针指向 root，继续遍历左子树
        		predecessor.right = root
                
        		# 改变根节点，并断开原根节点与左孩子的联系
            	tmp = root
                root = root.left
                tmp.left = None
            
            # 如果没有左孩子，则直接访问右孩子
            else:
            	res.append(root.val)
                root = root.right
        return res

码农公寓