剑指offer（17）——C++实现判断树的子树

野性酷女 2024-04-17 05:36 8阅读 0赞

# 题目 #

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

# 考察点 #

*  树、指针、递归

# 解题思路 #

二叉树的遍历常用递归实现。先从A的根节点开始判断，若相同再去判断A的左右子树节点。

# 完整代码 #

/*17-树的子结构*/
    #include<iostream>
    using namespace std;
    //树的创建
    struct TreeNode {
        
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {
        
    	}
    };
    class Solution {
        
    public:
    	bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    	{
        
    		bool  result = false;
    		if (pRoot1 == NULL || pRoot2 == NULL)
    			return false;
    		if (pRoot1->val == pRoot2->val)//判断A的根是不是B的根，是就进行节点值递归判断
    			result = isequal(pRoot1, pRoot2);
    		if (!result)//上面不是，就判断左节点
    			result = HasSubtree(pRoot1->left, pRoot2);
    		if(!result)//左节点还是，就判断右节点
    			result = HasSubtree(pRoot1->right, pRoot2);
    		return result;
    	}
    	//递归实现，节点比较
    	bool isequal(TreeNode* pRoot1, TreeNode* pRoot2)
    	{
        
    		if (pRoot2 == NULL) return true;//pRoot2为空表明B树已经走完
    		if (pRoot1 == NULL) return false;//
    		if (pRoot1->val == pRoot2->val)
    			return isequal(pRoot1->left, pRoot2->left) && isequal(pRoot1->right, pRoot2->right);
    		else
    			return false;
    	}
    };
    int main()
    {
        
    	TreeNode* A1 = new TreeNode(1); TreeNode* A2 = new TreeNode(2); TreeNode* A3 = new TreeNode(3);
    	TreeNode* A4= new TreeNode(4); TreeNode* A5 = new TreeNode(5); 
    	A1->left = A2; A1->right = A3; A2->left = A4; A2->right = A5;
    	TreeNode* B1 = new TreeNode(2); TreeNode* B2 = new TreeNode(3); TreeNode* B3 = new TreeNode(4);
    	B1->left = B2; B1->right = B3;
    	Solution s;
    	cout << s.HasSubtree(A1, B2) << endl;
    	return 0;
    }