题解 | #牛群的相似结构#

//发现题解都是用的递归，写了一个用栈优化的解法
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param p TreeNode类 
     * @param q TreeNode类 
     * @return bool布尔型
     */
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // write code here
        if (!p && !q) {
            return true;
        }
        else if (!p || !q) {
            return false;
        }
        //到此为止确保p,q都不为空，开始遍历
        std::stack<TreeNode*> stkp;
        std::stack<TreeNode*> stkq;
        stkp.push(p);
        stkq.push(q);
        while(!stkp.empty() && !stkq.empty()){
            p = stkp.top();
            q = stkq.top();
            stkp.pop();
            stkq.pop();
            if (p->val!=q->val) {
                return false;
            }
            if (p->right && q->right) {
                stkp.push(p->right);
                stkq.push(q->right);
            }
            else if(p->right || q->right){
                return false;
            }
            if (p->left && q->left) {
                stkp.push(p->left);
                stkq.push(q->left);
            }
            else if(p->left || q->left){
                return false;
            }
        }
        return true;
    }
};