层次结构分明的网站配色方案,建筑工程培训,学做网站开发吗,seo工具排行榜通过万岁#xff01;#xff01;#xff01;
题目#xff1a;给你一个完全二叉树#xff0c;然后将其奇数层进行反转。思路#xff1a;这个题他都说了是奇数层了#xff0c;那基本就是层序遍历了。但是存在两个问题#xff0c;一个是如何判断奇数层#xff0c;另外一…通过万岁
题目给你一个完全二叉树然后将其奇数层进行反转。思路这个题他都说了是奇数层了那基本就是层序遍历了。但是存在两个问题一个是如何判断奇数层另外一个是如何进行交换。首先是第一个问题如何判断是奇数层。这个问题比较简单由于我们每次往数组中添加的都是左右两个节点的元素。因此如果队列中的元素个数是2的n次方并且n是一个奇数则表示奇数层。然后就是反转了这里需要借助一个list集合我没有找到队列有反转的方法如果有的话空间复杂度可以小一点。值得注意的是在最后一层元素出队的时候也会遇到奇数层的情况所以我们需要记录层数层数必须是一直增加的。思路层序遍历队列。
java代码
class Solution {public TreeNode reverseOddLevels(TreeNode root) {if (root null || root.left null) {return root;}QueueTreeNode queue new LinkedList();queue.add(root);int r;int l;double level 0;while (queue.size() ! 0) {TreeNode remove queue.remove();if (remove.left ! null) {queue.add(remove.left);}if (remove.right ! null) {queue.add(remove.right);}r queue.size() - 1;l 0;double newLevel Math.log(r 1) / Math.log(2);if (newLevel level) {continue;} else {level newLevel;}// 如果是奇数层则就需要进行交换了if (newLevel % 2 1) {ListTreeNode transList new ArrayList(r);for (TreeNode treeNode : queue) {transList.add(treeNode);}while (r l) {int temp transList.get(r).val;transList.get(r).val transList.get(l).val;transList.get(l).val temp;l;r--;}}}return root;}
}总结其实这个问题比较简单的。
