- 剑指 Offer 面试题 18（Java 版）：树的子结构
题目：输入两棵二叉树 A 和 B，判断 B 是不是 A 的子结构。
例如图中所示的两棵二叉树，由于 A 中有一部分子树的结构和 B 是一样的，因此 B 是 A 的子结构。
例子
思路：第一步在树 A 中找到与树 B 根结点一样值的结点 R，第二步再判断树 A 中以 R 为根结点的子树是不是包含和树 B 一样的结构。
首先我们试着在树 A 中找到值为 8 的结点。从树 A 的根节点开始遍历，我们发现它的根节点的值就是 8。接着我们就去判断树 A 的根结点下面的子树是不是含有和树 B 一样的结构。在树 A 中，根结点的左子结点的值是 8，而树 B 的根节点的左子结点是 9，对应的两个结点不同。
因此我们仍然要遍历A，接着查找值为 8 的结点。我们在树的第二层中找到一个值为 8 的结点，然后进行第二步的判断，即判断这个结点下面的子树是否含有和树 B 一样结构的子树。于是我们遍历这个结点下面的子树，先后得到两个子结点 9 和 2，这和树 B 的结构完全相同。此时我们在树 A 中找到了一个和树 B 的结构一样的子树，因此树 B 和树 A 的子结构。
show my code
/**
* 二叉树结点
* @author innovator
*
*/
public class BinaryTreeNode {
public int value;
public BinaryTreeNode leftNode;
public BinaryTreeNode rightNode;
public BinaryTreeNode(int value){
this.value = value ;
}
}
/**
* 判断一个树 B 是不是 树 A 的子结构
* @author innovator
*
*/
public class SubstructureInTree {
/**
* 判断一个树 B 是不是 树 A 的子结构
* @param root1
* @param root2
* @return
*/
public static boolean hasSubTree(BinaryTreeNode root1,BinaryTreeNode root2){
//加入树 B 是空，假定包含
if(root2 == null){
return true;
}
if(root1 == null){
return false;
}
boolean result = false;
if(root1 != null && root2 != null){
//根结点的值一样
if(root1.value == root2.value){
//递归判断左右字树是否相同
result = doesTree1HaveTree2(root1, root2);
}
//如果根节点不一样，那就遍历左右子树，找到根结点的值一样的结点
if(!result){
result = hasSubTree(root1.leftNode,root2);
}
if(!result){
result = hasSubTree(root1.rightNode, root2);
}
}
return result;
}
/**
* 遍历左子树右子树，判断是否相等
* @param root1
* @param root2
* @return
*/
public static boolean doesTree1HaveTree2(BinaryTreeNode root1,BinaryTreeNode root2){
//已经比较完了 B 树的叶子结点
if(root2 == null){
return true;
}
//已经遍历到了 A 树的叶子结点
if(root1 == null){
return false;
}
if(root1.value != root2.value){
//如果根结点的值不相等，那么不用比较下面的子树了，就是不相等
return false;
}
//递归比较左子树，右子树的值
return doesTree1HaveTree2(root1.leftNode, root2.leftNode)
&& doesTree1HaveTree2(root1.rightNode, root2.rightNode);
}
public static void main(String[] args){
BinaryTreeNode A = new BinaryTreeNode(8);
BinaryTreeNode B = new BinaryTreeNode(8);
BinaryTreeNode C = new BinaryTreeNode(7);
BinaryTreeNode D = new BinaryTreeNode(9);
BinaryTreeNode E = new BinaryTreeNode(2);
BinaryTreeNode F = new BinaryTreeNode(4);
BinaryTreeNode G = new BinaryTreeNode(7);
BinaryTreeNode sub = new BinaryTreeNode(8);
BinaryTreeNode I = new BinaryTreeNode(9);
BinaryTreeNode J = new BinaryTreeNode(2);
A.leftNode = B;
A.rightNode = C;
B.leftNode = D;
B.rightNode = E;
E.leftNode = F;
E.rightNode = G;
sub.leftNode = I;
sub.rightNode = J;
System.out.println("树 sub 是 树 A 的子结构吗？"+ hasSubTree(A,sub));
}
}
测试结果
- 剑指 Offer 面试题 19（Java 版）：二叉树的镜像
题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像。
树的镜像是一个比较新的概念，我们未必能够一下子相出求树的镜像的方法。为了能够形成直观的印象，我们可以自己画一棵二叉树，然后根据镜子的经验画出它的镜像。
image
思路：我们得出求一棵树的镜像的过程：我们先前序遍历这棵树的每个结点，如果遍历的结点有子节点，就交换它的两个子节点，当交换完所有的非叶子结点的左右子节点之后，我们就得到了镜像。
show my code
/**
* 打印二叉树的镜像
* @author innovator
*
*/
public class TreeMirror {
/**
* 递归实现打印二叉树镜像
* @param root
* @return
*/
public static void mirrorByDigui(BinaryTreeNode root){
//空树
if(root == null){
return;
}
//叶子结点
if(root.leftNode == null && root.rightNode == null){
return;
}
//交换左右子结点
BinaryTreeNode temp = root.leftNode;
root.leftNode = root.rightNode;
root.rightNode = temp;
//递归交换左结点的左右字树
if(root.leftNode != null){
mirrorByDigui(root.leftNode);
}
//递归交换右结点的左右字树
if(root.rightNode != null){
mirrorByDigui(root.rightNode);
}
}
/**
* 借助辅助栈（后进先出）循环交换左右字树
* @param root
*/
public static void mirrorByStack(BinaryTreeNode root){
if(root == null){
return;
}
LinkedList<BinaryTreeNode> stack = new LinkedList<BinaryTreeNode>();//借助于辅助栈
BinaryTreeNode current = null;//存放出栈的栈顶元素
BinaryTreeNode temp = null; //交换左右结点用的临时变量
stack.push(root);//将根元素入栈
while(!stack.isEmpty()){
current = stack.pop();//将根元素出栈 交换根元素的左右子树
//若左右孩子不为空则交换左右孩子
if(current.leftNode != null || current.rightNode != null){
temp = current.leftNode;
current.leftNode = current.rightNode;
current.rightNode = temp;
}
//将根元素的左右孩子压入栈中
//这里其实是一层一层地交换左右子结点
if(current.leftNode != null){
stack.push(current.leftNode);
}
if(current.rightNode != null){
stack.push(current.rightNode);
}
}
}
/**
* 前序遍历打印
* @param root
*/
public static void printPreOrder(BinaryTreeNode root) {
if (root == null) {
return;
} else {
System.out.print(root.value + " ");
}
if (root.leftNode != null) {
printPreOrder(root.leftNode);
}
if (root.rightNode != null) {
printPreOrder(root.rightNode);
}
}
public static void main(String[] args){
BinaryTreeNode A = new BinaryTreeNode(8);
BinaryTreeNode B = new BinaryTreeNode(6);
BinaryTreeNode C = new BinaryTreeNode(10);
BinaryTreeNode D = new BinaryTreeNode(5);
BinaryTreeNode E = new BinaryTreeNode(7);
BinaryTreeNode F = new BinaryTreeNode(9);
BinaryTreeNode G = new BinaryTreeNode(11);
A.leftNode = B;
A.rightNode = C;
B.leftNode = D;
B.rightNode = E;
C.leftNode = F;
C.rightNode = G;
System.out.println("原始二叉树的前序遍历：");
printPreOrder(A);
System.out.println("");
// mirrorByDigui(A);
mirrorByStack(A);
System.out.println("镜像二叉树的前序遍历：");
printPreOrder(A);
}
}
结果
网友评论