反转二叉树的奇数层 图解题解

这道题到底在问什么

输入

root=[2,3,5,8,13,21,34]

输出

[2,5,3,8,13,21,34]

输入

root=[7,13,11]

输出

[7,11,13]

最优解：一步一步想明白

1. 3记牢这一句:偶数层不碰,奇数层用左右指针成对换值。下面从第 0 层开始,一层一层往下走。
2. 4根在第 0 层先把这棵树看清楚。它一共三层:最上面第 0 层是根 2;第 1 层是它的两个孩子 3 和 5;最下面第 2 层是四个叶子 8、13、21、34。层号从根算起是 0,往下依次加一。我们要动的只有奇数层,这棵树里就是第 1 层。
3. 5当前层号 i = 0层序遍历从根开始。把根 2 放进队列,现在处理第 0 层,这一层只有它一个节点。先看层号,i 等于 0。判断奇偶:0 是偶数,所以这一层不需要反转。
4. 6i = 0 偶数,跳过反转第 0 层是偶数层,直接跳过反转,值一个都不动。接着把根 2 的两个孩子按从左到右的顺序入队:先 3 后 5。它们组成下一层,也就是第 1 层的待处理队列。第 0 层就算处理完了。
5. 7当前层号 i = 1轮到第 1 层。这一层从左到右是两个节点 3 和 5,已经在队列里排好。处理任何一层的第一步,都是先问一句:这一层的层号是奇数还是偶数。这里 i 等于 1。
6. 8奇数层 → 需要反转算一下,1 除以 2 余 1,所以 1 是奇数,这是一个奇数层。奇数层就要做反转。反转的目标很明确:把这一排节点的值,从 3、5 变成 5、3,让整层顺序颠倒过来。
7. 9左指针指 3,右指针指 5反转用一对指针来做。左指针 l 站在这一层最左边,指着 3;右指针 r 站在最右边,指着 5。它们会从两头往中间走,一路把对称位置上的两个值成对交换。这一层只有两个节点,所以走一次就够了。
8. 10左端 = 3,右端 = 5交换前先把两端的值拿到手:左指针那里是 3,右指针那里是 5。注意我们只交换这两个节点里存的数字,节点本身和它连着的子树不动。对完美二叉树来说,只换值就等于把这一层的顺序翻过来。
9. 113 与 5 已互换一交换,左边的节点里现在是 5,右边的节点里现在是 3。你看树上第 1 层,已经从 3、5 变成了 5、3。这一步只改了两个节点存的数字,连线和它们各自的孩子都还在原地。
10. 12l 右移、r 左移,两者交叉交换后左指针往右挪一步、右指针往左挪一步,l 从 0 走到 1、r 从 1 走到 0,两个指针交叉了。指针交叉或相遇就代表这一层从两头到中间都换过了,反转到此结束。现在第 1 层稳稳是 5、3。
11. 13第 1 层 = 5, 3再确认一眼:第 0 层的根还是 2 没动,第 1 层已经反转成 5 在左、3 在右。奇数层的活儿干完了,接下来要为下一层做准备,把第 1 层这两个节点的孩子入队。
12. 14左节点孩子: 8, 13先看第 1 层左边这个节点,它现在存着 5。孩子按位置算是它下面挂的 8 和 13,注意交换的只是值,孩子还挂在原来的节点上。把 8、13 按从左到右的顺序放进队列。
13. 15右节点孩子: 21, 34再看第 1 层右边这个节点,它现在存着 3,下面挂的孩子是 21 和 34,继续入队。现在下一层的队列凑齐了,从左到右是 8、13、21、34,正好是第 2 层的四个节点。
14. 16当前层号 i = 2来到第 2 层,这一层从左到右是四个叶子 8、13、21、34。老规矩,先问层号奇偶。i 等于 2。
15. 17i = 2 偶数,不反转2 除以 2 余 0,是偶数,所以第 2 层跳过反转,四个值原封不动。接下来只需把这一层的节点一个个出队即可,因为它们都是叶子,底下没有孩子要入队了。
16. 188 出队,无孩子把第 2 层第一个节点 8 出队。它是叶子,底下没有孩子,所以什么都不用入队,处理它就是走个过场。
17. 1913 出队,无孩子再出队 13,同样是叶子。队列里的节点一个个被取走,底下没有新节点补进来,队列只会越来越短。
18. 2021 出队,无孩子出队 21,还是叶子。队列里现在只剩最后一个 34 了。
19. 2134 出队,队列将空出队最后一个 34,叶子,没有孩子。队列被取空了,再也没有下一层要处理。
20. 22所有层已处理队列空了,层序遍历结束。回头看这一趟:第 0 层偶数不动,第 1 层奇数已经反转成 5、3,第 2 层偶数不动。整棵树该翻的都翻了。
21. 23答案已成型最终这棵树,层序读出来就是 2、5、3、8、13、21、34。跟一开始预告的答案完全对上。全程唯一被改动的,就是第 1 层这个奇数层,3 和 5 交换成了 5 和 3。
22. 24偶数层原样,奇数层颠倒把整件事收成一句:偶数层第 0 层和第 2 层原样不动,只有奇数层第 1 层被颠倒了顺序,从 3、5 变成 5、3。反转靠的是左右指针成对交换节点里的值,树的结构和连线自始至终没变。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# 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 = deque([root])
        i = 0
        while q:
            if i & 1:
                level = list(q)
                l, r = 0, len(level) - 1
                while l < r:
                    level[l].val, level[r].val = level[r].val, level[l].val
                    l, r = l + 1, r - 1
            for _ in range(len(q)):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                    q.append(node.right)
            i += 1
        return root

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* reverseOddLevels(TreeNode* root) {
        queue<TreeNode*> q{{root}};
        for (int i = 0; q.size(); ++i) {
            vector<TreeNode*> t;
            for (int k = q.size(); k; --k) {
                TreeNode* node = q.front();
                q.pop();
                if (i & 1) {
                    t.push_back(node);
                }
                if (node->left) {
                    q.push(node->left);
                    q.push(node->right);
                }
            }
            for (int l = 0, r = t.size() - 1; l < r; ++l, --r) {
                swap(t[l]->val, t[r]->val);
            }
        }
        return root;
    }
};

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        Deque<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        for (int i = 0; !q.isEmpty(); ++i) {
            List<TreeNode> t = new ArrayList<>();
            for (int k = q.size(); k > 0; --k) {
                TreeNode node = q.poll();
                if (i % 2 == 1) {
                    t.add(node);
                }
                if (node.left != null) {
                    q.offer(node.left);
                    q.offer(node.right);
                }
            }
            for (int l = 0, r = t.size() - 1; l < r; ++l, --r) {
                int x = t.get(l).val;
                t.get(l).val = t.get(r).val;
                t.get(r).val = x;
            }
        }
        return root;
    }
}

复杂度

面试官可能追问