题解 | 树的子结构

/*
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){
		stack<TreeNode*> stk1;  //本例采用前序遍历的方法，根-左-右
		stack<TreeNode*> stk2;

		stk1.push(r1);
		stk2.push(r2);
		while(!stk2.empty()){  //第二个子树是模板，只用比较模板中存在的节点即可
			if( !stk1.top() || stk1.top()->val != stk2.top()->val) return false;

			TreeNode* node1 = stk1.top();stk1.pop();  
			TreeNode* node2 = stk2.top();stk2.pop();
			if(node2->right){           //只用比较模板有的，考虑结构（位置）是否相同：节点始终保持同步，位置相同；
				stk2.push(node2->right);
				stk1.push(node1->right);
			}
			if(node2->left){
				stk2.push(node2->left);		
				stk1.push(node1->left);
			}
		}

		return true;
	}
};