《剑指Offer》-26-树的子结构

没做过这种类型的题，树怎么比较？

我好像一下子不会写怎么用迭代写法遍历一棵树
嗯，看以前的笔记是用栈

这一题算是树的遍历的组合题

class Solution {
public:
	bool isSubStructure(TreeNode* A, TreeNode* B) {
		if (!B || !A) return false;
		stack<TreeNode*> stk;
		TreeNode* node = A;
		while (!stk.empty() || node != nullptr) {
			while (node != nullptr) {
				// 先访问根节点
				if (equalTree(node, B))return true;
				stk.emplace(node);
				node = node->left;
			}
			node = stk.top();
			stk.pop();
			node = node->right;
		}
		return false;
	}

	bool equalTree(TreeNode* root1, TreeNode* root2) {
		if (!root2) return true;
		if (!root1) return false;
		return root1->val == root2->val &&
			equalTree(root1->left, root2->left)
			&& equalTree(root1->right, root2->right);
	}
};