相同二叉树

虽然递归慢，但是写起来爽啊😁

虽然循环快，但是写起来磨啊😭

递归实现

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;
    }
};