题解 | #合并二叉树#用队列的思路

看到大部分题解都用的递归，这里放一个用队列的思路

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */

      TreeNode* mergeNode(TreeNode* t1, TreeNode* t2){
        TreeNode* r;
             if(t1||t2){
               r=
                new TreeNode(
                    (t1?t1->val:0)+(t2?t2->val:0)
                );

            }else{
                r=nullptr;
            }
             //cout<<'['<<(t1?t1->val:0)<<" "<<(t2?t2->val:0)<<" "<<(r?r->val:0)<<"]"<<endl;
            return r;
      }
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        // write code here
        TreeNode *cur1,*cur2,*cur1l,*cur1r,*cur2l,*cur2r,*cur3l,*cur3r,*cur3,*curLayerEnd1=t1,*curLayerEnd2=t2,*result=mergeNode(t1, t2);
        //cout<<result->val<<endl;
        int toLayerEnd=(bool)result;
        deque<TreeNode*> q1({t1}),q2({t2}),q3({result});
        bool isNextLayerEmpty=t1&&t2;


        while(1){
            
            cur1=q1.front();
            q1.pop_front();
            cur2=q2.front();
            q2.pop_front();
            cur3=q3.front();
            q3.pop_front();
            
            if(cur1||cur2){
                cur1l=cur1?cur1->left:nullptr;
                cur1r=cur1?cur1->right:nullptr;
                cur2l=cur2?cur2->left:nullptr;
                cur2r=cur2?cur2->right:nullptr;
                cur3l=mergeNode(cur1l,cur2l);
                cur3r=mergeNode(cur1r,cur2r);   
                q1.push_back(cur1l);
                q1.push_back(cur1r);
                q2.push_back(cur2l);
                q2.push_back(cur2r);
                q3.push_back(cur3l);
                q3.push_back(cur3r);
                cur3->left=cur3l;
                cur3->right=cur3r; 
                //cout<<'('<<cur3->val<< ' '<<(cur3l?cur3l->val:0)<<' '<<(cur3r?cur3r->val:0)<<")"<<endl;
            }
            if(cur3l||cur3r)isNextLayerEmpty=false;
            toLayerEnd--;
            if(!toLayerEnd){
                if(isNextLayerEmpty)break;
                isNextLayerEmpty=true;
                toLayerEnd=q1.size();
                }

            }
        return result;
    }
};