树的子结构(树每个结点递归)
树的子结构
http://www.nowcoder.com/questionTerminal/6e196c44c7004d15b1610b9afca8bd88
/*
f：判断A,B是否相等
递归出口：当A==NUll 返回 false; B==NUll返回true
当A->val==B->val 判断左右子树f(A->left,B->left)，f(A->right,A->right)；
否则返回false
HasSubtree 还要循环判断A中结点，与B中每一个结点比较,即f（A中任意一个结点，B）
返回当前结点，返回左右结点判断情况。
*/
class Solution {
public:
bool dfs(TreeNode *r1,TreeNode *r2){
if(!r2)return true;//B树分支遍历完，返回true
if(!r1)return false;//A树为空不匹配,B不是子结构,返回false·
return r1->val==r2->val && dfs(r1->left,r2->left) && dfs(r1->right,r2->right);
}
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
if(!pRoot1||!pRoot2)return false;//有一个树不存在返回false
return dfs(pRoot1,pRoot2)||HasSubtree(pRoot1->left, pRoot2)
||HasSubtree(pRoot1->right,pRoot2);
}
};
腾讯成长空间 5958人发布
投递哔哩哔哩等公司6个岗位