番禺人才网官方网站信息公布,建筑工地新型材料模板,微信企业邮箱登录入口,网页设计公司网易企业邮箱#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域新星创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ BFS | DFS 求解思路 实现代码 - BFS 运行结果 实现代码 - DFS 运行结果 共勉 题目链接
2415. 反转二叉树的奇数层
⛲ 题目描述
给你一棵 完美 二叉树的根节点 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 105 root 是一棵 完美 二叉树 求解思路实现代码运行结果 ⚡ BFS | DFS 求解思路
思路一通过BFS求解如果是奇数层需要先将结果记录然后进行反转即可。思路二通过DFS求解如果是奇数层交换节点的数值然后递归交换root1的左子树和root2的右子树同理递归root1的右子树和root2的左子树。实现代码如下所示 实现代码 - BFS
/*** 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) {QueueTreeNode queuenew LinkedList();queue.add(root);int cnt0;while(!queue.isEmpty()){int sizequeue.size();ListTreeNode listnew ArrayListTreeNode();for(int i0;isize;i){TreeNode tempqueue.poll();if(cnt%21) list.add(temp);if(temp.left!null){queue.add(temp.left);}if(temp.right!null){queue.add(temp.right);}}if(cnt%21){for (int l0,rsize-1;lr;l,r--) {int templist.get(l).val;list.get(l).vallist.get(r).val;list.get(r).valtemp;}}cnt;}return root;}
}运行结果 实现代码 - DFS
/*** 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) {dfs(root.left,root.right,1);return root;}public void dfs(TreeNode root1,TreeNode root2,int depth){if(root1null||root2null) return;if(depth%21){int temproot1.val;root1.valroot2.val;root2.valtemp;}dfs(root1.left,root2.right,depth1);dfs(root1.right,root2.left,depth1);}
}运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
