每日一题 2415. 反转二叉树的奇数层（中等，树）

1. 深度搜索整棵树，将奇数层的节点按照层数存在list中
2. 将每一层 list 中的节点的值反转
3. 这适用于所有二叉树，但题中的完美二叉树有更好的解法
4. 我们可以把 root.left 和 root.right 看成一对节点，首先它们本身是需要反转的，然后下一层的 root.left.left 和 root.right.right，root.left.right 和 root.right.left 可以变成两对，且如果需要反转的话，只需要将每一对反转即可
5. 可以看到，每一对节点传递到下一层可以变成两对节点，由于它是完美二叉树，这样的过程可以传递到最后一层，只需要将奇数层的节点对的值进行互换即可

class Solution:
    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        d = defaultdict(list)
        
        def dfs(node, deep):
            if node is None:
                return
            if deep % 2 == 1:
                d[deep].append(node)
            dfs(node.left, deep + 1)
            dfs(node.right, deep + 1)
        
        dfs(root, 0)

        i = 1
        while True:
            if i not in d:
                break
            n = len(d[i])
            for k in range(n // 2):
                d[i][k].val, d[i][n - k - 1].val =  d[i][n - k - 1].val, d[i][k].val
            i += 2
        return root

class Solution {
public:
    TreeNode* reverseOddLevels(TreeNode* root) {
        dfs(root->left, root->right, true);
        return root;
    }

    void dfs(TreeNode *root1, TreeNode *root2, bool isOdd) {
        if (root1 == nullptr) {
            return;
        }
        if (isOdd) {
            swap(root1->val, root2->val);
        }
        dfs(root1->left, root2->right, !isOdd);
        dfs(root1->right, root2->left, !isOdd);
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/reverse-odd-levels-of-binary-tree/solutions/2562073/fan-zhuan-er-cha-shu-de-qi-shu-ceng-by-l-n034/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。