做网站标签栏的图片大小,HTML做网站的书籍,交易类网站做支付宝功能,公司起名大全2023最新版的免费【LetMeFly】2415.反转二叉树的奇数层#xff1a;深度优先搜索(DFS)
力扣题目链接#xff1a;https://leetcode.cn/problems/reverse-odd-levels-of-binary-tree/
给你一棵 完美 二叉树的根节点 root #xff0c;请你反转这棵树中每个 奇数 层的节点值。
例如#xff0c…【LetMeFly】2415.反转二叉树的奇数层深度优先搜索(DFS)
力扣题目链接https://leetcode.cn/problems/reverse-odd-levels-of-binary-tree/
给你一棵 完美 二叉树的根节点 root 请你反转这棵树中每个 奇数 层的节点值。
例如假设第 3 层的节点值是 [2,1,3,4,7,11,29,18] 那么反转后它应该变成 [18,29,11,7,4,3,1,2] 。
反转后返回树的根节点。
完美 二叉树需满足二叉树的所有父节点都有两个子节点且所有叶子节点都在同一层。
节点的 层数 等于该节点到根节点之间的边数。 示例 1 输入root [2,3,5,8,13,21,34]
输出[2,5,3,8,13,21,34]
解释
这棵树只有一个奇数层。
在第 1 层的节点分别是 3、5 反转后为 5、3 。示例 2 输入root [7,13,11]
输出[7,11,13]
解释
在第 1 层的节点分别是 13、11 反转后为 11、13 。 示例 3
输入root [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]
输出[0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]
解释奇数层由非零值组成。
在第 1 层的节点分别是 1、2 反转后为 2、1 。
在第 3 层的节点分别是 1、1、1、1、2、2、2、2 反转后为 2、2、2、2、1、1、1、1 。提示
树中的节点数目在范围 [1, 214] 内0 Node.val 105root 是一棵 完美 二叉树
方法一深度优先搜索(DFS)
这道题不要真的交换节点因为交换节点会导致被交换节点的子节点顺序也发生变化。所谓“交换节点”其实只需要“交换节点的值”即可。
不难发现若某层需要发生交换只需要“第1个节点跟最后一个节点换”、“第2个节点跟倒数第二个节点换”、…
因此写一个函数dfs接收三个参数“节点1”、“节点2”、“是否需要交换”。在递归时将“节点1的left 和 节点2的right”放到一起递归“节点1的right 和 节点2的left”放到一起递归即可。
时间复杂度 O ( n ) O(n) O(n)其中 n n n是二叉树节点个数空间复杂度 O ( n ) O(n) O(n)
AC代码
C
class Solution {
private:void dfs(TreeNode* left, TreeNode* right, bool shouldReverse) {if (!left) {return ;}if (shouldReverse) {swap(left-val, right-val);}dfs(left-left, right-right, !shouldReverse);dfs(left-right, right-left, !shouldReverse);}
public:TreeNode* reverseOddLevels(TreeNode* root) {dfs(root-left, root-right, true);return root;}
};Python
# from typing import Optional# # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right rightclass Solution:def dfs(self, left: Optional[TreeNode], right: Optional[TreeNode], shouldReverse: bool) - None:if not left:returnif shouldReverse:left.val, right.val right.val, left.valself.dfs(left.left, right.right, not shouldReverse)self.dfs(left.right, right.left, not shouldReverse)def reverseOddLevels(self, root: TreeNode) - TreeNode:self.dfs(root.left, root.right, True)return root 同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/135020080
