*二叉树*用循环法和递归判断二叉树相等

题目详情

二叉树结构：

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

递归：

class Solution {
public:
    /**
     * 
     * @param p TreeNode类 
     * @param q TreeNode类 
     * @return bool布尔型
     */
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // write code here
        if(p==NULL&&q==NULL) return true;
        if(p==NULL||q==NULL) return false;
        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
        if(p==NULL&&q==NULL) return true;
        if(p==NULL||q==NULL) return false;
        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;

    }
};

循环版思路
建立两个栈a,b，用来存储p和q的节点
根据栈的特性，先存右节点再存左节点，这样取节点时就可以先取左节点再取右节点
并且每次循环都比较节点val，如若有不同则为不相等