虽然递归慢,但是写起来爽啊😁
虽然循环快,但是写起来磨啊😭
递归实现
class Solution { public: /** * * @param p TreeNode类 * @param q TreeNode类 * @return bool布尔型 */ bool isSameTree(TreeNode *p, TreeNode *q) { // write code here if (p == nullptr || q == nullptr) return p == q; if (p->val != q->val) return false; bool left = isSameTree(p->left, q->left); bool right = isSameTree(p->right, q->right); return left && right; } };
循环实现
class Solution { public: /** * * @param p TreeNode类 * @param q TreeNode类 * @return bool布尔型 */ bool isSameTree(TreeNode *p, TreeNode *q) { // write code here // 重要:同时空true,一空一非空false if (p == nullptr || q == nullptr) return p == q; stack<TreeNode *> a, b; a.push(p); b.push(q); while (!a.empty() && !b.empty()) { TreeNode *x = a.top(); TreeNode *y = b.top(); a.pop(); b.pop(); if (x->val != y->val) return false; if (x->right && y->right) { a.push(x->right); b.push(y->right); } else if (x->right || y->right) return false; if (x->left && y->left) { a.push(x->left); b.push(y->left); } else if (x->left || y->left) return false; } if (a.empty() && b.empty()) return true; else return false; } };