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.
Solutions
Solution 1: BFS
We can use the Breadth-First Search (BFS) method, using a queue $q$ to store the nodes of each level, and a variable $i$ to record the current level. If $i$ is odd, we reverse the values of the nodes at the current level.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 91011121314151617181920212223
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defreverseOddLevels(self,root:Optional[TreeNode])->Optional[TreeNode]:q=deque([root])i=0whileq:ifi&1:l,r=0,len(q)-1whilel<r:q[l].val,q[r].val=q[r].val,q[l].vall,r=l+1,r-1for_inrange(len(q)):node=q.popleft()ifnode.left:q.append(node.left)q.append(node.right)i+=1returnroot
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcreverseOddLevels(root*TreeNode)*TreeNode{q:=[]*TreeNode{root}fori:=0;len(q)>0;i++{t:=[]*TreeNode{}fork:=len(q);k>0;k--{node:=q[0]q=q[1:]ifi%2==1{t=append(t,node)}ifnode.Left!=nil{q=append(q,node.Left)q=append(q,node.Right)}}forl,r:=0,len(t)-1;l<r;l,r=l+1,r-1{t[l].Val,t[r].Val=t[r].Val,t[l].Val}}returnroot}