题目来源: 牛客网--二叉树的镜像
题目描述
操作给定的二叉树,将其变换为源二叉树的镜像
输入描述
二叉树的镜像定义:
源二叉树 :
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树:
8
/ \
10 6
/ \ / \
11 9 7 5
解题思路
首先要了解递归,理解节点之间是怎么相互链接的。 (递归不要想太深,只看眼前这一步,逐级向下带入,直到最终出口,再逐级向上回代执行。)
本题:遍历所有节点,每一个节点都判断是否为 null,不为 null 就说明此节点存在,然后直接互换左右子节点。对子节点进行判断,如果子节点为 null,就不进行递归,如果不为 null 就进行递归。(这样的好处是可以减少一层递归)
java代码
提交的代码
public void Mirror(TreeNode root) {
// 判断节点是否存在。
if (root == null) {
return;
}
// 交换左右子节点
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
// 判断左右节点是否存在,这样就少递归一层
if (root.left != null) {
Mirror(root.left);
}
if (root.right != null) {
Mirror(root.right);
}
}
本地测试代码
import java.util.Scanner;
public class mirrorTreeNode {
public static void main(String[] args) {
TreeNode root = new TreeNode(8);
// 生成测试 二叉树
input(root);
// 输出原始 二叉树
output(root);
// 二叉树镜像反转
mirror(root);
System.out.println("\n");
// 输出原始二叉树的 镜像
output(root);
}
// 因为嫌麻烦就把二叉树测试用例写死了
static void input(TreeNode root) {
TreeNode fl = new TreeNode(6);
TreeNode fr = new TreeNode(10);
TreeNode sl = new TreeNode(5);
TreeNode sr = new TreeNode(7);
root.left = fl;
root.right = fr;
fl.left = sl;
fl.right = sr;
}
// 输出函数,前序遍历(根节点最先,然后同级先左后右)
static void output(TreeNode root) {
System.out.print(root.val + " ");
if (root.left != null) {
output(root.left);
}
if (root.right != null) {
output(root.right);
}
}
// 二叉树镜像函数
public static void mirror(TreeNode root) {
if (root == null) {
return;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
if (root.left != null) {
mirror(root.left);
}
if (root.right != null) {
mirror(root.right);
}
}
}
/**
* 定义一个二叉树
*/
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
网友评论