LeetCode 199：二叉树右视图O(1)空间迭代解法问询

给定二叉树根节点，返回从右侧能看到的节点值（从上到下排列）。我已经实现了层序遍历的O(n)时空复杂度解法，现在需要一个迭代式、空间复杂度O(1)（除存储结果的数组外，不使用任何额外数据结构）的优化解法。

原O(n)时空解法 #

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    # time complexity: O(n), memory complexity: O(n)
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        res = []
        q = collections.deque([root])
        while q:
            len_q, level = len(q), []
            for _ in range(len_q):
                node = q.popleft()
                level.append(node)
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
            res.append(level[-1].val) # add the last element of each level (right most element)
        return res

O(1)空间迭代优化解法 #

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        current = root
        depth = 0
        
        while current:
            # 当前深度未记录过节点，说明是当前层最右节点
            if depth == len(res):
                res.append(current.val)
            
            # 优先遍历右子树
            if current.right:
                predecessor = current.left
                temp_depth = depth + 1
                if predecessor:
                    # 找到左子树的最右节点，且未建立回溯线索
                    while predecessor.right and predecessor.right != current:
                        predecessor = predecessor.right
                        temp_depth += 1
                    if not predecessor.right:
                        # 建立回溯线索，指向当前节点
                        predecessor.right = current
                        current = current.right
                        depth += 1
                    else:
                        # 断开线索，恢复树结构
                        predecessor.right = None
                        current = current.left
                        depth = temp_depth
                else:
                    # 无左子树，直接前往右子树
                    current = current.right
                    depth += 1
            else:
                # 无右子树，前往左子树
                current = current.left
                depth += 1
        
        return res

解法说明 #

这个解法基于莫里斯遍历的思路，通过利用叶子节点的空指针建立临时回溯线索，完全不需要栈、队列等额外数据结构：

1. 优先右子树遍历：确保首次到达某一深度的节点就是该层的最右节点，直接加入结果数组。
2. 线索回溯机制：对于有左子树的节点，找到左子树的最右节点并建立指向当前节点的线索，遍历完右子树后可通过线索返回，再处理左子树，处理完成后断开线索恢复树的原始结构。
3. 深度跟踪：通过维护当前节点的深度，判断是否到达新的层级，避免重复记录同一层的节点。

复杂度分析 #

• 时间复杂度：O(n)，每个节点最多被访问两次（一次建立线索，一次断开线索）。
• 空间复杂度：O(1)，仅使用了几个变量跟踪状态，结果数组不算额外空间（题目要求返回该数组）。

内容的提问来源于stack exchange，提问作者Benny