non-recursive. two queue Iteration


  • 0
    K
    
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        bool isSameTree(TreeNode* p, TreeNode* q) {
            if(p==NULL && q != NULL) return false;
            if(p!=NULL && q == NULL) return false;
            if(p==NULL && q == NULL) return true;
            if(p->val != q->val) return false;
            
            queue<TreeNode*> pnode,qnode;
            pnode.push(p);
            qnode.push(q);
            
        
            while(!pnode.empty() && !qnode.empty())
            {
                int np=pnode.size();
                int nq=qnode.size();
                if (np != nq)
                {
                  return false;
                }
                    
                for(int i=0;i<np;i++)
                {
                    TreeNode *p1=pnode.front();
                    pnode.pop();
                    TreeNode *q2=qnode.front();
                    qnode.pop();
                    
                    if(p1->val!=q2->val) return false;
                    
                    if(p1->left!=NULL) pnode.push(p1->left);
                    if(q2->left!=NULL) qnode.push(q2->left);
                    
                    //这里判断长度相等很巧妙,不然左右子树难以判断。
                    if(pnode.size()!=qnode.size()) return false;
                    
                    if(p1->right!=NULL) pnode.push(p1->right);
                    if(q2->right!=NULL) qnode.push(q2->right);
                    
                }
            }
            
            if (pnode.empty()&!qnode.empty() || !pnode.empty()&qnode.empty()) return false;
            return true;
    
        }
    };
    
    ~~~
    
    
    ~~~

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.