2415. 反转二叉树的奇数层

2415. 反转二叉树的奇数层

• 难度: medium
• 原始链接: https://leetcode.cn/problems/reverse-odd-levels-of-binary-tree
• 标签: 广度优先遍历, 深度优先遍历

解法一: 广度优先遍历

go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func reverseOddLevels(root *TreeNode) *TreeNode {
    if root == nil {
        return root
    }
    queue := []*TreeNode{root}
    isOdd := false
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            if queue[i].Left != nil {
                queue = append(queue, queue[i].Left, queue[i].Right)
            }
        }
        if isOdd {
            left := 0
            right := size - 1
            for left < right {
                queue[left].Val, queue[right].Val = queue[right].Val, queue[left].Val
                left++
                right--
            }
        }
        isOdd = !isOdd
        queue = queue[size:]
    }
    return root
}

解法二: 深度优先遍历

go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func reverseOddLevels(root *TreeNode) *TreeNode {
    var dfs func (node1, node2 *TreeNode, isOdd bool)
    dfs = func (node1, node2 *TreeNode, isOdd bool) {
        if node1 == nil || node2 == nil {
            return
        }
        if isOdd {
            node1.Val, node2.Val = node2.Val, node1.Val
        }
        dfs(node1.Left, node2.Right, !isOdd)
        dfs(node1.Right, node2.Left, !isOdd)
    }
    dfs(root.Left, root.Right, true)
    return root
}