题目
输入两颗二叉树A和B，判断B是否是A的子结构，例如下图中B是A的子结构
A B
思路
判断B是A的一部分，首先保证B的根节点的值与A中的某结点的值相同，在保证孩子结点也相同。
首先判断给定的树A,B中的两个指针pa, pb，判断pb的整体是不是以pa为根节点的一部分，采用的是递归做法
参考代码
bool IsPart(BinaryTreeNode *p1, BinaryTreeNode *p2) { if(p2 == NULL) return true; else if(p1 == NULL) return false; else { if(p1->m_nValue != p2->m_nValue) return false; else if(IsPart(p1->m_pLeft, p2->m_pLeft) && IsPart(p1->m_pRight, p2->m_pRight)) return true; } }
接着是B的头结点和A的结点对比一下，如果和A中的一个结点能得出B是A的一部分（即IsPart（pa, pb）=true）那么就可得出B是A中的一部分。
访问A中的结点，可以参考访问二叉树的递归遍历
void MidTranverse(BinaryTreeNode *root) { if(root != NULL) { MidTranverse(root->m_pLeft); cout << root->m_nValue << " "; MidTranverse(root->m_pRight); } }
但是这样在输出的位置，判断IsPart，结果怎么处置，我采用的方式是利用全局变量ISPART，起初是设为false，如果判断出IsPart(pa, pb)，就置ISPART=true。
参考代码1
bool HasPartTree(BinaryTreeNode *p1, BinaryTreeNode *p2) { if(p2 == NULL) return false; if(p1 != NULL) { HasPartTree(p1->m_pLeft, p2); if(IsPart(p1, p2)) ISPART = true; //全局变量 HasPartTree(p1->m_pRight, p2); } return false; }
整体运行
#include <iostream> using namespace std; bool ISPART = false; struct BinaryTreeNode { int m_nValue; BinaryTreeNode *m_pLeft; BinaryTreeNode *m_pRight; }; void CreateTree1(BinaryTreeNode *root) { BinaryTreeNode *p1 = new(BinaryTreeNode); p1->m_nValue = 8; p1->m_pLeft = NULL; p1->m_pRight = NULL; root->m_pLeft = p1; BinaryTreeNode *p2 = new(BinaryTreeNode); p2->m_nValue = 7; p2->m_pLeft = NULL; p2->m_pRight = NULL; root->m_pRight = p2; BinaryTreeNode *p3 = new(BinaryTreeNode); p3->m_nValue = 9; p3->m_pLeft = NULL; p3->m_pRight = NULL; p1->m_pLeft = p3; BinaryTreeNode *p4 = new(BinaryTreeNode); p4->m_nValue = 2; p4->m_pLeft = NULL; p4->m_pRight = NULL; p1->m_pRight = p4; BinaryTreeNode *p5 = new(BinaryTreeNode); p5->m_nValue = 4; p5->m_pLeft = NULL; p5->m_pRight = NULL; p4->m_pLeft = p5; BinaryTreeNode *p6 = new(BinaryTreeNode); p6->m_nValue = 7; p6->m_pLeft = NULL; p6->m_pRight = NULL; p4->m_pRight = p6; } void CreateTree2(BinaryTreeNode *root) { BinaryTreeNode *p1 = new(BinaryTreeNode); p1->m_nValue = 9; p1->m_pLeft = NULL; p1->m_pRight = NULL; root->m_pLeft = p1; BinaryTreeNode *p2 = new(BinaryTreeNode); p2->m_nValue = 2; p2->m_pLeft = NULL; p2->m_pRight = NULL; root->m_pRight = p2; } void MidTranverse(BinaryTreeNode *root) { if(root != NULL) { MidTranverse(root->m_pLeft); cout << root->m_nValue << " "; MidTranverse(root->m_pRight); } } void DeleteTree(BinaryTreeNode *root) { if(root != NULL) { DeleteTree(root->m_pLeft); DeleteTree(root->m_pRight); delete(root); root = NULL; } } bool IsPart(BinaryTreeNode *p1, BinaryTreeNode *p2) { if(p2 == NULL) return true; else if(p1 == NULL) return false; else { if(p1->m_nValue != p2->m_nValue) return false; else if(IsPart(p1->m_pLeft, p2->m_pLeft) && IsPart(p1->m_pRight, p2->m_pRight)) return true; } } bool HasPartTree(BinaryTreeNode *p1, BinaryTreeNode *p2) { if(p2 == NULL) return false; if(p1 != NULL) { HasPartTree(p1->m_pLeft, p2); if(IsPart(p1, p2)) ISPART = true; HasPartTree(p1->m_pRight, p2); } return false; } int main() { BinaryTreeNode *tree_1 = new(BinaryTreeNode); BinaryTreeNode *tree_2 = new(BinaryTreeNode); tree_1->m_nValue = 8; tree_1->m_pLeft = NULL; tree_1->m_pRight = NULL; tree_2->m_nValue = 8; tree_2->m_pLeft = NULL; tree_2->m_pRight = NULL; CreateTree1(tree_1); CreateTree2(tree_2); HasPartTree(tree_1, tree_2); ISPART = false; cout << "ISPAET:" << ISPART << endl; DeleteTree(tree_1); DeleteTree(tree_2); /* MidTranverse(tree_1); cout << endl; MidTranverse(tree_2); cout << endl; */ }
参考了《剑指offer》的做法，仍然是递归，不采用全局变量的做法
参考代码2
bool HasPartTree(BinaryTreeNode *p1, BinaryTreeNode *p2) { bool result = false; if(p1 != NULL && p2 != NULL) { if(p1->m_nValue == p2->m_nValue) result = IsPart(p1, p2); if(!result) result = HasPartTree(p1->m_pLeft, p2); if(!result) result = HasPartTree(p1->m_pRight, p2); } return result; }
整体运行
#include <iostream> using namespace std; struct BinaryTreeNode { int m_nValue; BinaryTreeNode *m_pLeft; BinaryTreeNode *m_pRight; }; void CreateTree1(BinaryTreeNode *root) { BinaryTreeNode *p1 = new(BinaryTreeNode); p1->m_nValue = 8; p1->m_pLeft = NULL; p1->m_pRight = NULL; root->m_pLeft = p1; BinaryTreeNode *p2 = new(BinaryTreeNode); p2->m_nValue = 7; p2->m_pLeft = NULL; p2->m_pRight = NULL; root->m_pRight = p2; BinaryTreeNode *p3 = new(BinaryTreeNode); p3->m_nValue = 9; p3->m_pLeft = NULL; p3->m_pRight = NULL; p1->m_pLeft = p3; BinaryTreeNode *p4 = new(BinaryTreeNode); p4->m_nValue = 2; p4->m_pLeft = NULL; p4->m_pRight = NULL; p1->m_pRight = p4; BinaryTreeNode *p5 = new(BinaryTreeNode); p5->m_nValue = 4; p5->m_pLeft = NULL; p5->m_pRight = NULL; p4->m_pLeft = p5; BinaryTreeNode *p6 = new(BinaryTreeNode); p6->m_nValue = 7; p6->m_pLeft = NULL; p6->m_pRight = NULL; p4->m_pRight = p6; } void CreateTree2(BinaryTreeNode *root) { BinaryTreeNode *p1 = new(BinaryTreeNode); p1->m_nValue = 9; p1->m_pLeft = NULL; p1->m_pRight = NULL; root->m_pLeft = p1; BinaryTreeNode *p2 = new(BinaryTreeNode); p2->m_nValue = 2; p2->m_pLeft = NULL; p2->m_pRight = NULL; root->m_pRight = p2; } void MidTranverse(BinaryTreeNode *root) { if(root != NULL) { MidTranverse(root->m_pLeft); cout << root->m_nValue << " "; MidTranverse(root->m_pRight); } } void DeleteTree(BinaryTreeNode *root) { if(root != NULL) { DeleteTree(root->m_pLeft); DeleteTree(root->m_pRight); delete(root); root = NULL; } } bool IsPart(BinaryTreeNode *p1, BinaryTreeNode *p2) { if(p2 == NULL) return true; else if(p1 == NULL) return false; else { if(p1->m_nValue != p2->m_nValue) return false; else if(IsPart(p1->m_pLeft, p2->m_pLeft) && IsPart(p1->m_pRight, p2->m_pRight)) return true; } } bool HasPartTree(BinaryTreeNode *p1, BinaryTreeNode *p2) { bool result = false; if(p1 != NULL && p2 != NULL) { if(p1->m_nValue == p2->m_nValue) result = IsPart(p1, p2); if(!result) result = HasPartTree(p1->m_pLeft, p2); if(!result) result = HasPartTree(p1->m_pRight, p2); } return result; } int main() { BinaryTreeNode *tree_1 = new(BinaryTreeNode); BinaryTreeNode *tree_2 = new(BinaryTreeNode); tree_1->m_nValue = 8; tree_1->m_pLeft = NULL; tree_1->m_pRight = NULL; tree_2->m_nValue = 8; tree_2->m_pLeft = NULL; tree_2->m_pRight = NULL; CreateTree1(tree_1); CreateTree2(tree_2); cout << "Result:" << HasPartTree(tree_1->m_pRight, tree_2) << endl; DeleteTree(tree_1); DeleteTree(tree_2); }
原文：http://www.cnblogs.com/kaituorensheng/p/3617810.html
