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^14] 内
  • 0 <= Node.val <= 10^5
  • root 是一棵 完美二叉树

解题思路

解题思路

这道题要求反转完美二叉树的奇数层节点值。有两种主要的解法思路：

方法一：层序遍历 + 反转（推荐）

使用 BFS 进行层序遍历，记录当前层数。当层数为奇数时，收集该层所有节点的值并反转，然后重新赋值给节点。这种方法思路直观，易于理解。

方法二：深度优先搜索

利用完美二叉树的性质，在 DFS 过程中同时传递左右两个应该配对的节点。如果当前层是奇数层，则交换这两个节点的值，否则递归处理下一层。

两种方法都能正确解决问题，但层序遍历的方法更容易理解和实现，特别是对于处理整层数据的情况。深度优先搜索的方法利用了完美二叉树的对称性质，代码更加简洁。

我们将采用层序遍历的方法作为主要解法，因为它更直观且容易扩展到其他类似问题。

代码实现

class Solution {
public:
    TreeNode* reverseOddLevels(TreeNode* root) {
        if (!root) return root;
        
        queue<TreeNode*> q;
        q.push(root);
        int level = 0;
        
        while (!q.empty()) {
            int size = q.size();
            vector<TreeNode*> nodes;
            
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                nodes.push_back(node);
                
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            
            if (level % 2 == 1) {
                int left = 0, right = nodes.size() - 1;
                while (left < right) {
                    swap(nodes[left]->val, nodes[right]->val);
                    left++;
                    right--;
                }
            }
            
            level++;
        }
        
        return root;
    }
};

class Solution:
    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return root
        
        queue = [root]
        level = 0
        
        while queue:
            size = len(queue)
            nodes = []
            
            for _ in range(size):
                node = queue.pop(0)
                nodes.append(node)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            if level % 2 == 1:
                left, right = 0, len(nodes) - 1
                while left < right:
                    nodes[left].val, nodes[right].val = nodes[right].val, nodes[left].val
                    left += 1
                    right -= 1
            
            level += 1
        
        return root

public class Solution {
    public TreeNode ReverseOddLevels(TreeNode root) {
        if (root == null) return root;
        
        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        int level = 0;
        
        while (queue.Count > 0) {
            int size = queue.Count;
            List<TreeNode> nodes = new List<TreeNode>();
            
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.Dequeue();
                nodes.Add(node);
                
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
            
            if (level % 2 == 1) {
                int left = 0, right = nodes.Count - 1;
                while (left < right) {
                    int temp = nodes[left].val;
                    nodes[left].val = nodes[right].val;
                    nodes[right].val = temp;
                    left++;
                    right--;
                }
            }
            
            level++;
        }
        
        return root;
    }
}

var reverseOddLevels = function(root) {
    if (!root) return root;
    
    let queue = [root];
    let level = 0;
    
    while (queue.length > 0) {
        let size = queue.length;
        let currentLevel = [];
        
        for (let i = 0; i < size; i++) {
            let node = queue.shift();
            currentLevel.push(node);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        if (level % 2 === 1) {
            let values = currentLevel.map(node => node.val);
            values.reverse();
            for (let i = 0; i < currentLevel.length; i++) {
                currentLevel[i].val = values[i];
            }
        }
        
        level++;
    }
    
    return root;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
层序遍历O(n)O(w)

其中 n 是树中节点的总数，w 是树的最大宽度。对于完美二叉树，最大宽度为 O(n/2)，所以空间复杂度为 O(n)。

相关题目