LeetCode 2415. 反转二叉树的奇数层：深度优先搜索(DFS)

【LetMeFly】2415.反转二叉树的奇数层：深度优先搜索(DFS)

力扣题目链接：https://leetcode.cn/problems/reverse-odd-levels-of-binary-tree/

给你一棵完美二叉树的根节点 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 是一棵完美二叉树

方法一：深度优先搜索(DFS)

这道题不要真的交换节点，因为交换节点会导致被交换节点的子节点顺序也发生变化。所谓“交换节点”，其实只需要“交换节点的值”即可。

不难发现，若某层需要发生交换，只需要“第1个节点跟最后一个节点换”、“第2个节点跟倒数第二个节点换”、…

因此写一个函数dfs，接收三个参数“节点1”、“节点2”、“是否需要交换”。在递归时，将“节点1的left 和节点2的right”放到一起递归，“节点1的right 和节点2的left”放到一起递归即可。

时间复杂度 $O (n)$ ，其中 $n$ 是二叉树节点个数
空间复杂度 $O (n)$

AC代码

C++

class Solution {
private:
    void dfs(TreeNode* left, TreeNode* right, bool shouldReverse) {
        if (!left) {
            return ;
        }
        if (shouldReverse) {
            swap(left->val, right->val);
        }
        dfs(left->left, right->right, !shouldReverse);
        dfs(left->right, right->left, !shouldReverse);
    }
public:
    TreeNode* reverseOddLevels(TreeNode* root) {
        dfs(root->left, root->right, true);
        return root;
    }
};

Python

# from typing import Optional

# # 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 dfs(self, left: Optional[TreeNode], right: Optional[TreeNode], shouldReverse: bool) -> None:
        if not left:
            return
        if shouldReverse:
            left.val, right.val = right.val, left.val
        self.dfs(left.left, right.right, not shouldReverse)
        self.dfs(left.right, right.left, not shouldReverse)

    def reverseOddLevels(self, root: TreeNode) -> TreeNode:
        self.dfs(root.left, root.right, True)
        return root