问题
判断一棵树是否是另一棵树的子树，如图
思路
问题分两步：
- 找值相同的根结点（遍历解决）
- 判断两结点是否包含（递归：值、左孩子、右孩子分别相同）
树节点定义
struct TreeNode { int val; TreeNode *next; TreeNode(int v) : val(v), next(NULL) {} };
代码
bool IsPart(TreeNode *root1, TreeNode *root2) { if (root2 == NULL) return true; if (root1 == NULL) return false; if (root1->val != root2->val) return false; return IsPart(root1->left, root2->left) && IsPart(root1->right, root2->right); } bool IsPartTree(TreeNode *root1, TreeNode *root2) { bool result = false; if (root1 != NULL && root2 != NULL) { if (root1->val == root2->val) result = IsPart(root1, root2); if (!result) result = IsPartTree(root1->left, root2); if (!result) result = IsPartTree(root1->right, root2); } return result; }
执行
View Code
推荐
本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/p/4215688.html，如需转载请自行联系原作者
