2415. Reverse Odd Levels of Binary Tree

, ,

BFS

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
class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int level = 0;
        while (!queue.isEmpty()) {
            List<TreeNode> nodeList = new ArrayList<>(queue.size());
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                nodeList.add(node);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            if ((level & 1) == 1) {
                reverseNodeValue(nodeList);
            }
            level++;
        }

        return root;
    }

    private void reverseNodeValue(List<TreeNode> nodeList) {
        int i = 0, j = nodeList.size() - 1;
        while (i < j) {
            int tmp = nodeList.get(i).val;
            nodeList.get(i).val = nodeList.get(j).val;
            nodeList.get(j).val = tmp;
            i++;
            j--;
        }
    }
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        dfs(root.left, root.right, 1); // 注意传入的起始层数，因为首次进入了下层，所以传入为 1
        return root;
    }

    private void dfs(TreeNode left, TreeNode right, int level) {
        if (left == null) {
            return;
        }

        if ((level & 1) == 1) {
            int tmp = left.val;
            left.val = right.val;
            right.val = tmp;
        }

        dfs(left.left, right.right, level + 1);
        dfs(left.right, right.left, level + 1);
    }
}

References

2415. Reverse Odd Levels of Binary Tree