156 Binary Tree Upside Down 上下翻转二叉树
Description:
Given the root of a binary tree, turn the tree upside down and return the new root.
You can turn a binary tree upside down with the following steps:
The original left child becomes the new root.
The original root becomes the new right child.
The original right child becomes the new left child.
The mentioned steps are done level by level. It is guaranteed that every right node has a sibling (a left node with the same parent) and has no children.
[图片上传失败...(image-11d2f2-1667312067680)]
Example:
Example 1:
[图片上传失败...(image-8308e-1667312067680)]
Input: root = [1,2,3,4,5]
Output: [4,5,2,null,null,3,1]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [1]
Output: [1]
Constraints:
The number of nodes in the tree will be in the range [0, 10].
1 <= Node.val <= 10
Every right node in the tree has a sibling (a left node that shares the same parent).
Every right node in the tree has no children.
标题形貌：
给你一个二叉树的根节点 root ，请你将此二叉树上下翻转，并返回新的根节点。
你可以按下面的步调翻转一棵二叉树：
原来的左子节点酿成新的根节点
原来的根节点酿成新的右子节点
原来的右子节点酿成新的左子节点
上面的步调逐层举行。标题数据包管每个右节点都有一个同级节点（即共享同一父节点的左节点）且不存在子节点。
[图片上传失败...(image-c164cf-1667312067680)]
示例：
示例 1：
[图片上传失败...(image-21b272-1667312067680)]
输入：root = [1,2,3,4,5]
输出：[4,5,2,null,null,3,1]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
树中节点数量在范围 [0, 10] 内
1 <= Node.val <= 10
树中的每个右节点都有一个同级节点（即共享同一父节点的左节点）
树中的每个右节点都没有子节点
思绪：
模拟
记录末了返回的结点为 parent 也是根结点, 这个结点现实上应该是二叉树最左下角的结点
记录 parent 的右结点为 parent_right
先记录 root 的左结点 root_left
将 parent_right 赋予 root.left, 可从示例 1 的第三层和第二层明白
然后更新 parent_right 为 root -> right 和 root -> right 为 parent
末了 root 向左移动
时间复杂度为 O(n), 空间复杂度为 O(1)
代码:
C++: |
