Leetcode刷题100天—226.翻转二叉树(二叉树)—day06
【摘要】 前言:作者:神的孩子在歌唱大家好,我叫运智层序遍历示例:输入: 4 / \ 2 7 / \ / \1 3 6 9输出: 4 / \ 7 2 / \ / \9 6 3 1备注:这个问题是受到 Max Howell 的 原问题 启发的 :谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板...
前言:
作者:神的孩子在歌唱
大家好,我叫运智
层序遍历
示例:
输入:
4
/ \
2 7
/ \ / \
1 3 6 9
输出:
4
/ \
7 2
/ \ / \
9 6 3 1
备注:
这个问题是受到 Max Howell 的 原问题 启发的 :
谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/invert-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
package 二叉树;
import java.util.LinkedList;
import java.util.Queue;
/*
* 1
* https://leetcode-cn.com/problems/invert-binary-tree/
* 翻转一颗二叉树就是将其所有左右节点的左右子树都交换,也就是需要遍历所有节点,前序遍历
*/
public class _226_翻转二叉树<E> {
public TreeNode invertTree(TreeNode root) {
// 前序遍历,先访问自己,在访问左右
if (root==null) return root;
// 先遍历头节点的子树
TreeNode tmp=root.left;
root.left=root.right;
root.right=tmp;
// 再用递归方法遍历左右子树,先遍历左或者右都没关系
invertTree(root.left);
invertTree(root.right);
return root;
}
public TreeNode invertTree1(TreeNode root) {
// 方法二:后序遍历,先访问左右,在访问自己
if (root==null) return root;
// 先用递归方法遍历左右子树,先遍历左或者右都没关系
invertTree(root.left);
invertTree(root.right);
// 在将左右子树调换
TreeNode tmp=root.left;
root.left=root.right;
root.right=tmp;
return root;
}
public TreeNode invertTree2(TreeNode root) {
// 方法三:中序遍历,先访问左,在自己(头节点),在右
if (root==null) return root;
// 先用递归方法遍历左子树
invertTree(root.left);
// 在将左右子树调换
TreeNode tmp=root.left;
root.left=root.right;
root.right=tmp;
// 这里注意不能写right,因为上边已经将左右子树调换了,right已经变成left了。
invertTree(root.left);
return root;
}
public TreeNode invertTree3(TreeNode root) {
// 方法四:层序遍历,从上到下,从左到右一次访问每一个节点
if (root==null) return root;
// 创建队列,队列里面放节点TreeNode
Queue<TreeNode> queue=new LinkedList<>();
// 将根节点入队
queue.offer(root);
// 循环遍历,只要队列不为空,我就不断去除队列的头节点
while(!queue.isEmpty()) {
// 出队
TreeNode node=queue.poll();
// System.out.print(node.element);
// 将队头里面的元素左右交换
TreeNode tmp=node.left;
node.left=node.right;
node.right=tmp;
// 如果发现左右节点有值就入队
if(node.left!=null) {
queue.offer(node.left);
}
if (node.right!=null) {
queue.offer(node.right);
}
}
return root;
}
}
本人csdn博客:https://blog.csdn.net/weixin_46654114
转载说明:跟我说明,务必注明来源,附带本人博客连接。
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)