反转二叉树的奇数层

标签: 树深度优先搜索广度优先搜索二叉树

难度: Medium

给你一棵完美二叉树的根节点 root ，请你反转这棵树中每个奇数层的节点值。

例如，假设第 3 层的节点值是 [2,1,3,4,7,11,29,18] ，那么反转后它应该变成 [18,29,11,7,4,3,1,2] 。

反转后，返回树的根节点。

完美二叉树需满足：二叉树的所有父节点都有两个子节点，且所有叶子节点都在同一层。

节点的层数等于该节点到根节点之间的边数。

示例 1：

输入：root = [2,3,5,8,13,21,34]
输出：[2,5,3,8,13,21,34]
解释：
这棵树只有一个奇数层。
在第 1 层的节点分别是 3、5 ，反转后为 5、3 。

示例 2：

输入：root = [7,13,11]
输出：[7,11,13]
解释： 
在第 1 层的节点分别是 13、11 ，反转后为 11、13 。

示例 3：

输入：root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]
输出：[0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]
解释：奇数层由非零值组成。
在第 1 层的节点分别是 1、2 ，反转后为 2、1 。
在第 3 层的节点分别是 1、1、1、1、2、2、2、2 ，反转后为 2、2、2、2、1、1、1、1 。

提示：

树中的节点数目在范围 [1, 2¹⁴] 内
0 <= Node.val <= 10⁵
root 是一棵完美二叉树

Submission

运行时间: 129 ms

内存: 20.4 MB

# 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 reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        q = [root]
        level = 1
        while q[0].left:
            nxt = []
            for node in q:
                nxt.append(node.left)
                nxt.append(node.right)
            q = nxt
            if level:
                for i in range(len(q)//2):
                    x, y = q[i], q[len(q)-1-i]
                    x.val, y.val = y.val, x.val
            level ^= 1
        return root

Explain

此题解采用层序遍历的方法来访问和修改完美二叉树的奇数层节点。首先，使用一个队列来存储当前层的所有节点。通过循环，每次都将当前层的所有子节点添加到下一层的队列中。对于每一层，如果是奇数层（从0开始计数，所以实际的奇数层在代码中用偶数1表示），则在队列中将该层的节点值进行反向交换，从而实现每个奇数层的节点值反转。层序遍历继续，直到队列中的节点没有子节点为止。

时间复杂度: O(n)

空间复杂度: 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:
    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        q = [root]  # 初始化队列，开始时只包含根节点
        level = 1  # 用于标记当前层是奇数层还是偶数层，1 表示下一层是奇数层
        while q[0].left:  # 只要队列中有节点且有子节点
            nxt = []  # 下一层节点的列表
            for node in q:  # 遍历当前层的所有节点
                nxt.append(node.left)  # 添加左子节点到下一层
                nxt.append(node.right)  # 添加右子节点到下一层
            q = nxt  # 更新队列为下一层的节点
            if level:  # 如果当前层是奇数层
                for i in range(len(q)//2):  # 遍历到中间位置
                    x, y = q[i], q[len(q)-1-i]  # 选取要交换的一对节点
                    x.val, y.val = y.val, x.val  # 交换值
            level ^= 1  # 切换层级标记
        return root  # 返回修改后的树的根节点

Explore

在完美二叉树中，如果一个节点有子节点，那么它的所有同层节点也必然有子节点。因此，检查队列中第一个节点是否有左子节点足以判断整个层是否有子节点。这样的检查简化了逻辑，提高了代码的效率。

通过引入一个变量`level`来跟踪当前层的奇偶性。初始时`level`设为1，表示下一层（第一层）是奇数层。每处理完一层后，使用`level ^= 1`操作来切换`level`的值，从而跟踪接下来的层是奇数还是偶数层。

从列表两端向中间交换值是实现列表元素反转的一个有效方法。这种方式确保了在单次遍历中完成整层节点值的反转，节省时间和空间。从两端向中间交换直到中点，确保了每个节点的值只被交换一次。

在Python中，`x.val, y.val = y.val, x.val`是一种常用的并且安全的元素交换方式，它利用了Python的元组解包和打包特性。然而，在一些不支持多重赋值或元组打包解包的编程语言中，这种直接交换的写法可能会导致错误或需要额外的临时变量来完成交换。例如，在C或Java中，通常需要一个临时变量来安全地交换两个变量的值。