算法:翻转二叉树的左右节点
算法 大约 3038 字示例
翻转一棵二叉树。
4
/ \
2 7
/ \ / \
1 3 6 9
输出
4
/ \
7 2
/ \ / \
9 6 3 1
深度优先搜索
使用递归方式交换左右节点。
public Node invert(Node root) {
if (root == null) {
return null;
}
Node temp = root.left;
root.left = root.right;
root.right = temp;
invert(root.left);
invert(root.right);
return root;
}
广度优先搜索
使用队列方式交换左右节点,和层序遍历二叉树一样。
public Node invertBfs(Node root) {
if (root == null) {
return null;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
Node temp = node.left;
node.left = node.right;
node.right = temp;
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
return root;
}
完整代码
public class TreeInvert {
public static void main(String[] args) {
TreeInvert tree = new TreeInvert();
int[] arr = {4, 2, 7, 1, 3, 6, 9};
for (int i : arr) {
Node node = new Node(i);
tree.add(node);
}
// tree.invertR(tree.root);
tree.invertBfs(tree.root);
System.out.println(tree.root.id);
System.out.println(tree.root.left.id);
System.out.println(tree.root.right.id);
System.out.println(tree.root.left.left.id);
System.out.println(tree.root.left.right.id);
System.out.println(tree.root.right.left.id);
System.out.println(tree.root.right.right.id);
}
public Node root;
public Node invertBfs(Node root) {
if (root == null) {
return null;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
Node temp = node.left;
node.left = node.right;
node.right = temp;
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
return root;
}
public Node invertR(Node root) {
if (root == null) {
return null;
}
Node temp = root.left;
root.left = root.right;
root.right = temp;
invertR(root.left);
invertR(root.right);
return root;
}
public void add(Node node) {
root = add(root, node);
}
public Node add(Node rootNode, Node node) {
if (rootNode == null) {
return node;
}
if (rootNode.id > node.id) {
rootNode.left = add(rootNode.left, node);
} else {
rootNode.right = add(rootNode.right, node);
}
return rootNode;
}
private static class Node {
public int id;
public Node left;
public Node right;
public Node(int id) {
this.id = id;
}
}
}
LeetCode 原题地址
阅读 840 · 发布于 2021-02-26
————        END        ————
Give me a Star, Thanks:)
https://github.com/fendoudebb扫描下方二维码关注公众号和小程序↓↓↓

昵称:
随便看看
换一批
-
Android 使用 adb 命令录制视频阅读 4186
-
Golang 加密算法之 sha1阅读 1778
-
移动端 input 输入框使软键盘回车键变为搜索按钮阅读 3965
-
JavaScript 展开语法(三个点 ...)阅读 478
-
Windows10 Hyper-V 安装 CentOS阅读 613
-
使用 MyBatis 注解接收 PostgreSQL 的 returning 结果阅读 3728
-
Java G1 垃圾收集器开启字符串去重阅读 1465
-
Android item 填充时最外层布局高度失效解决办法阅读 1664
-
软考-系统架构设计师:网络存储技术 - Raid阅读 1539
-
SonarQube Lombok Malicious code error阅读 419