習(xí)慣github pages風(fēng)格的請(qǐng)看我的另一篇博客
題目27：
- 二叉樹的鏡像
- 對(duì)稱的二叉樹
題目：二叉樹的鏡像
請(qǐng)完成一個(gè)函數(shù)，輸入一個(gè)二叉樹曹货，該函數(shù)輸出它的鏡像。
二叉樹節(jié)點(diǎn)
public static class BinaryTreeNode {
int value;
BinaryTreeNode left;
BinaryTreeNode right;
public BinaryTreeNode(){
}
public BinaryTreeNode(int value){
this.value = value;
}
}
舉例說明
原二叉樹：（中序遍歷：5 6 7 8 9 10 11）
8
/ \
6 10
/ \ / \
5 7 9 11
鏡像二叉樹：（中序遍歷：11 10 9 8 7 6 5）
8
/ \
10 6
/ \ / \
11 9 7 5
思路
二叉樹的鏡像相當(dāng)于是將每個(gè)含有子結(jié)點(diǎn)的結(jié)點(diǎn)的左右子結(jié)點(diǎn)進(jìn)行交換健爬。利用遞歸實(shí)現(xiàn)控乾。
左右子結(jié)點(diǎn)進(jìn)行交換
代碼實(shí)現(xiàn)
public class _27{
public static class BinaryTreeNode {
int value;
BinaryTreeNode left;
BinaryTreeNode right;
public BinaryTreeNode(){
}
public BinaryTreeNode(int value){
this.value = value;
}
}
public static void mirrorRecursively(BinaryTreeNode node){
if(node == null) {
return;
}
if(node.left == null && node.right == null) {
return;
}
BinaryTreeNode temp = node.left;
node.left= node.right;
node.right = temp;
if(node.left != null)
mirrorRecursively(node.left);
if(node.right != null)
mirrorRecursively(node.right);
}
public static void printTree(BinaryTreeNode node) {
if (node != null) {
printTree(node.left);
System.out.print(node.value + " ");
printTree(node.right);
}
}
public static void main(String[] args) {
// 8
// / \
// 6 10
// / \ / \
// 5 7 9 11
BinaryTreeNode n1 = new BinaryTreeNode(8);
BinaryTreeNode n2 = new BinaryTreeNode(6);
BinaryTreeNode n3 = new BinaryTreeNode(10);
BinaryTreeNode n4 = new BinaryTreeNode(5);
BinaryTreeNode n5 = new BinaryTreeNode(7);
BinaryTreeNode n6 = new BinaryTreeNode(9);
BinaryTreeNode n7 = new BinaryTreeNode(11);
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
n3.left = n6;
n3.right = n7;
printTree(n1);
System.out.println();
mirrorRecursively(n1);
printTree(n1);
}
}
二叉樹的鏡像
題目：對(duì)稱的二叉樹
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，用來判斷一棵二叉樹是不是對(duì)稱的娜遵。如果二叉樹和它的鏡像一樣蜕衡，那么它是對(duì)稱的。
舉例說明
8
/ \
6 10
/ \ / \
5 7 9 11 不是對(duì)稱的二叉樹
8
/ \
6 6
/ \ / \
5 7 7 5 是對(duì)稱的二叉樹
思路
如果一顆二叉樹是對(duì)稱的，需要滿足：
- 當(dāng)前節(jié)點(diǎn)的值相等
- 節(jié)點(diǎn)的左子樹對(duì)稱慨仿，節(jié)點(diǎn)的右子樹對(duì)稱
注意這里的對(duì)稱久脯，是說鏡像相同。而鏡像與原來的是反的镰吆。即左子樹的左子樹與右子樹的右子樹相同帘撰。
代碼實(shí)現(xiàn)
public class _28{
public static class BinaryTreeNode {
int value;
BinaryTreeNode left;
BinaryTreeNode right;
public BinaryTreeNode(){
}
public BinaryTreeNode(int value){
this.value = value;
}
}
public static boolean isSymmetrical(BinaryTreeNode Root) {
if (Root == null)
return true;
return isSymmetrical(Root.left, Root.right);
}
private static boolean isSymmetrical(BinaryTreeNode left, BinaryTreeNode right) {
if (left == null && right == null)//都是空
return true;
if (left == null || right == null)//只有一個(gè)空
return false;
if (left.value != right.value)
return false;
return isSymmetrical(left.left, right.right) && isSymmetrical(left.right, right.left);
}
public static void main(String[] args) {
BinaryTreeNode n1 = new BinaryTreeNode(8);
BinaryTreeNode n2 = new BinaryTreeNode(6);
BinaryTreeNode n3 = new BinaryTreeNode(10);
BinaryTreeNode n4 = new BinaryTreeNode(5);
BinaryTreeNode n5 = new BinaryTreeNode(7);
BinaryTreeNode n6 = new BinaryTreeNode(9);
BinaryTreeNode n7 = new BinaryTreeNode(11);
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
n3.left = n6;
n3.right = n7;
System.out.println(isSymmetrical(n1));
BinaryTreeNode n8 = new BinaryTreeNode(8);
BinaryTreeNode n9 = new BinaryTreeNode(6);
BinaryTreeNode n10 = new BinaryTreeNode(6);
BinaryTreeNode n11 = new BinaryTreeNode(5);
BinaryTreeNode n12 = new BinaryTreeNode(7);
BinaryTreeNode n13 = new BinaryTreeNode(7);
BinaryTreeNode n14 = new BinaryTreeNode(5);
n8.left = n9;
n8.right = n10;
n9.left = n11;
n9.right = n12;
n10.left = n13;
n10.right = n14;
System.out.println(isSymmetrical(n8));
}
}
非遞歸：
import java.util.Stack;
public class _28 {
public static class BinaryTreeNode {
int value;
BinaryTreeNode left;
BinaryTreeNode right;
public BinaryTreeNode() {
}
public BinaryTreeNode(int value) {
this.value = value;
}
}
public static boolean isSymmetrical(BinaryTreeNode root) {
if (root == null) {
return true;
}
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
stack.push(root.left);
stack.push(root.right);
while (!stack.empty()) {
BinaryTreeNode p1 = stack.pop();
BinaryTreeNode p2 = stack.pop();
if (p1 == null && p2 == null) {
continue;
}
if (p1 == null || p2 == null || p1.value != p2.value) {
return false;
}
stack.push(p1.left);
stack.push(p2.right);
stack.push(p1.right);
stack.push(p2.left);
}
return true;
}
public static void main(String[] args) {
BinaryTreeNode n1 = new BinaryTreeNode(8);
BinaryTreeNode n2 = new BinaryTreeNode(6);
BinaryTreeNode n3 = new BinaryTreeNode(10);
BinaryTreeNode n4 = new BinaryTreeNode(5);
BinaryTreeNode n5 = new BinaryTreeNode(7);
BinaryTreeNode n6 = new BinaryTreeNode(9);
BinaryTreeNode n7 = new BinaryTreeNode(11);
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
n3.left = n6;
n3.right = n7;
System.out.println(isSymmetrical(n1));
BinaryTreeNode n8 = new BinaryTreeNode(8);
BinaryTreeNode n9 = new BinaryTreeNode(6);
BinaryTreeNode n10 = new BinaryTreeNode(6);
BinaryTreeNode n11 = new BinaryTreeNode(5);
BinaryTreeNode n12 = new BinaryTreeNode(7);
BinaryTreeNode n13 = new BinaryTreeNode(7);
BinaryTreeNode n14 = new BinaryTreeNode(5);
n8.left = n9;
n8.right = n10;
n9.left = n11;
n9.right = n12;
n10.left = n13;
n10.right = n14;
System.out.println(isSymmetrical(n8));
}
}
對(duì)稱的二叉樹
