题解 | 树的子结构

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
#include <stack>
class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
		if(!pRoot1 || !pRoot2)return false;

		stack<TreeNode*> stk;
		stk.push(pRoot1);

		while(!stk.empty()){
			TreeNode* node = stk.top();stk.pop();
			if(node->val == pRoot2->val && cheakif(node, pRoot2)){
				return true;
			}
			if(node->right)stk.push(node->right);
			if(node->left)stk.push(node->left);
		}

		return false;
    }

	bool cheakif(TreeNode* r1, TreeNode* r2){
		if(!r2){
			return true;
		}else{
			if(!r1)return false;
			else{
				if(r1->val != r2->val){return false;}
				else{
					return cheakif(r1->right, r2->right) && cheakif(r1->left, r2->left);
				}
			}
		}
	}
};