描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
基本思路
按照树 A 中每个节点的遍历顺序比较当前节点和 B 的根节点是否相同，如果相同就按照 B 的结构遍历他们的每个节点。
例子是题目所给的样例：
A : {8,8,#,9,#,2,#,5}
B : {8,9,#,2}
1.两个节点都是 8 ，根节点相同，开始遍历其他节点。
-
第二个节点不相同函数结束
-
继续比较 A 中节点和 B 的根节点，再次发现相同
-
按照 B 的顺序遍历所有节点发现 B 是 A 的子树
复杂度分析
在最坏情况下， 把 A 遍历了一遍，并且对于每个根节点都把 B 遍历了一遍，假设 A 和 B 分别有 m, n 个节点， 所以最坏的时间复杂度是 O（m * n）。
算法实现
详尽的注释都写在 c++ 版本的代码中。
- 递归方式
// c++
class Solution {
public:
// 函数返回子树 p1 和 p2 是否有相同结构
bool isSub(TreeNode* p1, TreeNode* p2) {
if (!p2) return true;
else if (!p1) return false;
// p1 和 p2 的根节点相同并且 p1 和 p2 的左子树和右子树分别相同
return p1->val == p2->val && isSub(p1->left, p2->left) && isSub(p1->right, p2->right);
}
// 函数返回树 p1 中是否有子树 p2
bool HasSubtree(TreeNode* p1, TreeNode* p2) {
if (!p1 || !p2) return false;
// p1 和 p2 结构相同，或者 p1 左子树或者右子树中有 p2
return isSub(p1, p2) || HasSubtree(p1->left, p2) || HasSubtree(p1->right, p2);
}
};
# python3
class Solution:
def isSub(self, p1, p2):
if not p2: return True
if not p1: return False
return p1.val == p2.val and self.isSub(p1.left, p2.left) and self.isSub(p1.right, p2.right)
def HasSubtree(self, p1, p2):
if not p1 or not p2: return False
return self.isSub(p1, p2) or self.HasSubtree(p1.left, p2) or self.HasSubtree(p1.right, p2)
- 非递归方式
// c++
class Solution {
public:
bool isSub(TreeNode* p1, TreeNode* p2) {
if (!p2) return true;
if (!p1) return false;
return p1->val == p2->val && isSub(p1->left, p2->left) && isSub(p1->right, p2->right);
}
// 中序遍历的方式遍历树 p1
bool HasSubtree(TreeNode* p1, TreeNode* p2) {
if (!p2) return false;
stack<TreeNode*> st;
while (p1 || !st.empty()) {
while (p1) {
if (p1->val == p2->val && isSub(p1, p2)) return true;
st.push(p1);
p1 = p1->left;
}
TreeNode* t = st.top();
st.pop();
p1 = t->right;
}
return false;
}