题目：输入两棵二叉树A和B，判断B是不是A的子结构。二叉树结点的定义如下：
struct BinaryTreeNode{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
}
代码实现：
package com.yyq; /** * Created by Administrator on 2015/9/15. */ public class SubstructureInTree { public static boolean hashSubTree(BinaryTreeNode pRoot1, BinaryTreeNode pRoot2) { boolean result = false; if (pRoot1 != null && pRoot2 != null) { if (pRoot1.getM_nValue() == pRoot2.getM_nValue()) { result = doesTree1HaveTree2(pRoot1, pRoot2); } if (!result) { result = hashSubTree(pRoot1.getM_pLeft(), pRoot2); } if (!result) { result = hashSubTree(pRoot1.getM_pRight(), pRoot2); } } return result; } public static boolean doesTree1HaveTree2(BinaryTreeNode pRoot1, BinaryTreeNode pRoot2) { if (pRoot2 == null) return true; if (pRoot1 == null) return false; if (pRoot1.getM_nValue() != pRoot2.getM_nValue()) return false; return doesTree1HaveTree2(pRoot1.getM_pLeft(), pRoot2.getM_pLeft()) && doesTree1HaveTree2(pRoot1.getM_pRight(), pRoot2.getM_pRight()); } // ====================测试代码==================== public static void Test(String testName, BinaryTreeNode pRoot1, BinaryTreeNode pRoot2, boolean expected) { if (hashSubTree(pRoot1, pRoot2) == expected) System.out.println(testName + " passed."); else System.out.println(testName + " fail."); } // 树中结点含有分叉，树B是树A的子结构 // 8 8 // / \ / \ // 8 7 9 2 // / \ // 9 2 // / \ // 4 7 public static void Test1() { BinaryTreeNode pNodeA1 = new BinaryTreeNode(8); BinaryTreeNode pNodeA2 = new BinaryTreeNode(8); BinaryTreeNode pNodeA3 = new BinaryTreeNode(7); BinaryTreeNode pNodeA4 = new BinaryTreeNode(9); BinaryTreeNode pNodeA5 = new BinaryTreeNode(2); BinaryTreeNode pNodeA6 = new BinaryTreeNode(4); BinaryTreeNode pNodeA7 = new BinaryTreeNode(7); pNodeA1.connectTreeNodes(pNodeA2, pNodeA3); pNodeA2.connectTreeNodes(pNodeA4, pNodeA5); pNodeA5.connectTreeNodes(pNodeA6, pNodeA7); BinaryTreeNode pNodeB1 = new BinaryTreeNode(8); BinaryTreeNode pNodeB2 = new BinaryTreeNode(9); BinaryTreeNode pNodeB3 = new BinaryTreeNode(2); pNodeB1.connectTreeNodes(pNodeB2, pNodeB3); Test("Test1", pNodeA1, pNodeB1, true); pNodeA1 = null; pNodeB1 = null; } // 树中结点含有分叉，树B不是树A的子结构 // 8 8 // / \ / \ // 8 7 9 2 // / \ // 9 3 // / \ // 4 7 public static void Test2() { BinaryTreeNode pNodeA1 = new BinaryTreeNode(8); BinaryTreeNode pNodeA2 = new BinaryTreeNode(8); BinaryTreeNode pNodeA3 = new BinaryTreeNode(7); BinaryTreeNode pNodeA4 = new BinaryTreeNode(9); BinaryTreeNode pNodeA5 = new BinaryTreeNode(3); BinaryTreeNode pNodeA6 = new BinaryTreeNode(4); BinaryTreeNode pNodeA7 = new BinaryTreeNode(7); pNodeA1.connectTreeNodes(pNodeA2, pNodeA3); pNodeA2.connectTreeNodes(pNodeA4, pNodeA5); pNodeA5.connectTreeNodes(pNodeA6, pNodeA7); BinaryTreeNode pNodeB1 = new BinaryTreeNode(8); BinaryTreeNode pNodeB2 = new BinaryTreeNode(9); BinaryTreeNode pNodeB3 = new BinaryTreeNode(2); pNodeB1.connectTreeNodes(pNodeB2, pNodeB3); Test("Test2", pNodeA1, pNodeB1, false); pNodeA1 = null; pNodeB1 = null; } // 树中结点只有左子结点，树B是树A的子结构 // 8 8 // / / // 8 9 // / / // 9 2 // / // 2 // / // 5 public static void Test3() { BinaryTreeNode pNodeA1 = new BinaryTreeNode(8); BinaryTreeNode pNodeA2 = new BinaryTreeNode(8); BinaryTreeNode pNodeA3 = new BinaryTreeNode(9); BinaryTreeNode pNodeA4 = new BinaryTreeNode(2); BinaryTreeNode pNodeA5 = new BinaryTreeNode(5); pNodeA1.connectTreeNodes(pNodeA2, null); pNodeA2.connectTreeNodes(pNodeA3, null); pNodeA3.connectTreeNodes(pNodeA4, null); pNodeA4.connectTreeNodes(pNodeA5, null); BinaryTreeNode pNodeB1 = new BinaryTreeNode(8); BinaryTreeNode pNodeB2 = new BinaryTreeNode(9); BinaryTreeNode pNodeB3 = new BinaryTreeNode(2); pNodeB1.connectTreeNodes(pNodeB2, null); pNodeB2.connectTreeNodes(pNodeB3, null); Test("Test3", pNodeA1, pNodeB1, true); pNodeA1 = null; pNodeB1 = null; } // 树中结点只有左子结点，树B不是树A的子结构 // 8 8 // / / // 8 9 // / / // 9 3 // / // 2 // / // 5 public static void Test4() { BinaryTreeNode pNodeA1 = new BinaryTreeNode(8); BinaryTreeNode pNodeA2 = new BinaryTreeNode(8); BinaryTreeNode pNodeA3 = new BinaryTreeNode(9); BinaryTreeNode pNodeA4 = new BinaryTreeNode(2); BinaryTreeNode pNodeA5 = new BinaryTreeNode(5); pNodeA1.connectTreeNodes(pNodeA2, null); pNodeA2.connectTreeNodes(pNodeA3, null); pNodeA3.connectTreeNodes(pNodeA4, null); pNodeA4.connectTreeNodes(pNodeA5, null); BinaryTreeNode pNodeB1 = new BinaryTreeNode(8); BinaryTreeNode pNodeB2 = new BinaryTreeNode(9); BinaryTreeNode pNodeB3 = new BinaryTreeNode(3); pNodeB1.connectTreeNodes(pNodeB2, null); pNodeB2.connectTreeNodes(pNodeB3, null); Test("Test4", pNodeA1, pNodeB1, false); pNodeA1 = null; pNodeB1 = null; } // 树中结点只有右子结点，树B是树A的子结构 // 8 8 // \ \ // 8 9 // \ \ // 9 2 // \ // 2 // \ // 5 public static void Test5() { BinaryTreeNode pNodeA1 = new BinaryTreeNode(8); BinaryTreeNode pNodeA2 = new BinaryTreeNode(8); BinaryTreeNode pNodeA3 = new BinaryTreeNode(9); BinaryTreeNode pNodeA4 = new BinaryTreeNode(2); BinaryTreeNode pNodeA5 = new BinaryTreeNode(5); pNodeA1.connectTreeNodes(null, pNodeA2); pNodeA2.connectTreeNodes(null, pNodeA3); pNodeA3.connectTreeNodes(null, pNodeA4); pNodeA4.connectTreeNodes(null, pNodeA5); BinaryTreeNode pNodeB1 = new BinaryTreeNode(8); BinaryTreeNode pNodeB2 = new BinaryTreeNode(9); BinaryTreeNode pNodeB3 = new BinaryTreeNode(2); pNodeB1.connectTreeNodes(null, pNodeB2); pNodeB2.connectTreeNodes(null, pNodeB3); Test("Test5", pNodeA1, pNodeB1, true); pNodeA1 = null; pNodeB1 = null; } // 树A中结点只有右子结点，树B不是树A的子结构 // 8 8 // \ \ // 8 9 // \ / \ // 9 3 2 // \ // 2 // \ // 5 public static void Test6() { BinaryTreeNode pNodeA1 = new BinaryTreeNode(8); BinaryTreeNode pNodeA2 = new BinaryTreeNode(8); BinaryTreeNode pNodeA3 = new BinaryTreeNode(9); BinaryTreeNode pNodeA4 = new BinaryTreeNode(2); BinaryTreeNode pNodeA5 = new BinaryTreeNode(5); pNodeA1.connectTreeNodes(null, pNodeA2); pNodeA2.connectTreeNodes(null, pNodeA3); pNodeA3.connectTreeNodes(null, pNodeA4); pNodeA4.connectTreeNodes(null, pNodeA5); BinaryTreeNode pNodeB1 = new BinaryTreeNode(8); BinaryTreeNode pNodeB2 = new BinaryTreeNode(9); BinaryTreeNode pNodeB3 = new BinaryTreeNode(3); BinaryTreeNode pNodeB4 = new BinaryTreeNode(2); pNodeB1.connectTreeNodes(null, pNodeB2); pNodeB2.connectTreeNodes(pNodeB3, pNodeB4); Test("Test6", pNodeA1, pNodeB1, false); pNodeA1 = null; pNodeB1 = null; } // 树A为空树 public static void Test7() { BinaryTreeNode pNodeB1 = new BinaryTreeNode(8); BinaryTreeNode pNodeB2 = new BinaryTreeNode(9); BinaryTreeNode pNodeB3 = new BinaryTreeNode(3); BinaryTreeNode pNodeB4 = new BinaryTreeNode(2); pNodeB1.connectTreeNodes(null, pNodeB2); pNodeB2.connectTreeNodes(pNodeB3, pNodeB4); Test("Test7", null, pNodeB1, false); pNodeB1 = null; } // 树B为空树 public static void Test8() { BinaryTreeNode pNodeA1 = new BinaryTreeNode(8); BinaryTreeNode pNodeA2 = new BinaryTreeNode(9); BinaryTreeNode pNodeA3 = new BinaryTreeNode(3); BinaryTreeNode pNodeA4 = new BinaryTreeNode(2); pNodeA1.connectTreeNodes(null, pNodeA2); pNodeA2.connectTreeNodes(pNodeA3, pNodeA4); Test("Test8", pNodeA1, null, false); pNodeA1 = null; } // 树A和树B都为空 public static void Test9() { Test("Test9", null, null, false); } public static void main(String[] args) { Test1(); Test2(); Test3(); Test4(); Test5(); Test6(); Test7(); Test8(); Test9(); } }
输出结果：
Test1 passed.
Test2 passed.
Test3 passed.
Test4 passed.
Test5 passed.
Test6 passed.
Test7 passed.
Test8 passed.
Test9 passed.