6182. 反转二叉树的奇数层（层次遍历）

问题描述

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

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

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

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

---

示例

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

---

【思路】：
用层次遍历，拿到每一层的序列。然后把奇数层用链表串起来，将问题转化为逆置链表即可。可以直接在树上进行修改。

---

【代码】：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

var level = function(root){
    let que = [];
    root.level = 0;
    que.push(root);
    let map = new Map();
    while(que.length != 0){
        let front = que.shift();
        let val = map.get(front.level);
        if(val == undefined){
            map.set(front.level, [front])
        }else{
            val.push(front);
            map.set(front.level, val)
        } 
        if(front.left != null){
            front.left.level = front.level + 1;
            que.push(front.left);
        }
        if(front.right != null){
            front.right.level = front.level + 1;
            que.push(front.right);
        }
    }
    return map;
}

var build = function(map){
	//对每一层建立链表串起来
    for(let item of map){ 
        let arr = item[1];
        let p = arr[0];
        for(let i = 1;i < arr.length;i++){
            p.next = arr[i];
            p = p.next;
        }
        p.next = null;
    }
    //对奇数层进行反转
    for(let item of map){ 
        if(item[0] % 2 != 0){
            let arr = item[1];
            let p = arr[0];
            let temp = []; 
            while(p != null){
                temp.push(p.val);
                p = p.next;
            }
            temp = temp.reverse();
            let i = 0;
            p = arr[0];
            while(p != null){
                p.val = temp[i];
                i++;
                p = p.next;
            }
        }
    }
}
 

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var reverseOddLevels = function(root) {
    var map = level(root); 
    //根据这个map建立一个层序链表
    build(map);
    return root;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79