2415. Reverse Odd Levels of Binary Tree

Leetcode link

题目简介

题目给我们一个完美二叉树（所有父节点都有两个子节点且所有叶子节点都在同一层），要求我们将奇数层的所有叶子节点翻转（简单理解成 Array.reverse() 就好

解题思路

其实翻转的本质可以看成，有两个指针分别指向需要交换的层的最左边与最右边的节点，然后将其交换后把指针各自往中间走一步，直到指针相遇

那么我们在树中要怎么样找到当前层最左跟最右的节点呢？答案是 dfs

我们只需要在深度遍历的时候，同时遍历两个节点就好了，所以 dfs 的调用应该是这样的：

dfs(node.left, node.right, level)

那么我们接下来要怎么让两个 “指针” 同时往中间走呢？答案是反过来遍历：

dfs(node.right, node.left, level)

基于以上，我们可以看代码了

Javascript

/**
 * 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)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var reverseOddLevels = function(root) {
    const dfs = (left, right, level) => {
        if(left === null || right === null) {
            return
        }
        if(level % 2 === 1) {
            [left.val, right.val] = [right.val, left.val]
        }
        dfs(left.left, right.right, level+1)
        dfs(left.right, right.left, level+1)
    }

    dfs(root.left, root.right, 1)
    return root

};