LeetCode——2415. 反转二叉树的奇数层
2023-12-23 00:03:23
通过万岁!!!
- 题目:给你一个完全二叉树,然后将其奇数层进行反转。
- 思路:这个题他都说了是奇数层了,那基本就是层序遍历了。但是存在两个问题,一个是如何判断奇数层,另外一个是如何进行交换。首先是第一个问题,如何判断是奇数层。这个问题比较简单,由于我们每次往数组中添加的都是左右两个节点的元素。因此,如果队列中的元素个数是2的n次方,并且n是一个奇数,则表示奇数层。然后就是反转了,这里需要借助一个list集合,我没有找到队列有反转的方法,如果有的话,空间复杂度可以小一点。值得注意的是,在最后一层元素出队的时候,也会遇到奇数层的情况,所以我们需要记录层数,层数必须是一直增加的。
- 思路:层序遍历,队列。
java代码
class Solution {
public TreeNode reverseOddLevels(TreeNode root) {
if (root == null || root.left == null) {
return root;
}
Queue<TreeNode> 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) {
List<TreeNode> 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;
}
}
- 总结:其实这个问题比较简单的。
文章来源:https://blog.csdn.net/qq_39056803/article/details/135162055
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!