Given the root of a perfect binary tree, reverse the node values at each odd level of the tree.
For example, suppose the node values at level 3 are [2,1,3,4,7,11,29,18], then it should become [18,29,11,7,4,3,1,2].
Return the root of the reversed tree.
A binary tree is perfect if all parent nodes have two children and all leaves are on the same level.
The level of a node is the number of edges along the path between it and the root node.
Example 1:
Input: root = [2,3,5,8,13,21,34]
Output: [2,5,3,8,13,21,34]
Explanation:
The tree has only one odd level.
The nodes at level 1 are 3, 5 respectively, which are reversed and become 5, 3.
Example 2:
Input: root = [7,13,11]
Output: [7,11,13]
Explanation:
The nodes at level 1 are 13, 11, which are reversed and become 11, 13.
Example 3:
Input: root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]
Output: [0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]
Explanation:
The odd levels have non-zero values.
The nodes at level 1 were 1, 2, and are 2, 1 after the reversal.
The nodes at level 3 were 1, 1, 1, 1, 2, 2, 2, 2, and are 2, 2, 2, 2, 1, 1, 1, 1 after the reversal.
Constraints:
The number of nodes in the tree is in the range [1, 214].
0 <= Node.val <= 105
root is a perfect binary tree.
反转二叉树的奇数层。
给你一棵 完美 二叉树的根节点 root ,请你反转这棵树中每个 奇数 层的节点值。
例如,假设第 3 层的节点值是 [2,1,3,4,7,11,29,18] ,那么反转后它应该变成 [18,29,11,7,4,3,1,2] 。
反转后,返回树的根节点。
完美 二叉树需满足:二叉树的所有父节点都有两个子节点,且所有叶子节点都在同一层。
节点的 层数 等于该节点到根节点之间的边数。
思路
这里我提供一个 前序遍历/DFS 的思路,我需要一个 helper 函数,因为需要统计当前层的深度。如果遇到奇数层,则需要交换当前层的左右两个节点。这个 helper 函数是从第二层开始的因为第一层只有 root 一个节点。
复杂度
时间O(n)
空间O(n)
代码
Java实现
/**
* 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 Solution {
public TreeNode reverseOddLevels(TreeNode root) {
helper(root.left, root.right, 1);
return root;
}
private void helper(TreeNode left, TreeNode right, int depth) {
if (left == null) {
return;
}
if (depth % 2 == 1) {
int temp = left.val;
left.val = right.val;
right.val = temp;
}
helper(left.right, right.left, depth + 1);
helper(left.left, right.right, depth + 1);
}
}
- LeetCode Reverse Binary Levels 2415leetcode reverse binary levels reverse strings binary leetcode maximum binary depth leetcode ancestor common binary leetcode binary add 67 leetcode longest binary zigzag leetcode validate binary nodes leetcode possible binary trees maximum-width-of-binary-tree leetcode problems unique-binary-search-trees leetcode unique binary