题解 | #合并二叉树#

最近状态及其差

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

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
      if (t1 == nullptr || t2 == nullptr) {
        return t1 == nullptr ? t2 : t1;
      }
      
      TreeNode *head = new TreeNode(t1->val + t2->val);
      std::queue<TreeNode *> queue_1, queue_2, queue_3;
      queue_1.push(t1), queue_2.push(t2), queue_3.push(head);
      
      while (!queue_1.empty() && !queue_2.empty()) {
        TreeNode *ptr_1 = queue_1.front(), *ptr_2 = queue_2.front(), *ptr_3 = queue_3.front();
        queue_1.pop(), queue_2.pop(), queue_3.pop();
        
        if (ptr_1->left || ptr_2->left) {
          if (ptr_1->left && ptr_2->left) {
            TreeNode *left = new TreeNode(ptr_1->left->val + ptr_2->left->val);
            ptr_3->left = left;
            queue_3.push(ptr_3->left);
            queue_1.push(ptr_1->left);
            queue_2.push(ptr_2->left);
          } else if (ptr_1->left) {
            ptr_3->left = ptr_1->left;
          } else {
            ptr_3->left = ptr_2->left;
          }
        }
        if (ptr_1->right || ptr_2->right) {
           if (ptr_1->right && ptr_2->right) {
            TreeNode *right = new TreeNode(ptr_1->right->val + ptr_2->right->val);
            ptr_3->right = right;
            queue_3.push(ptr_3->right);
            queue_1.push(ptr_1->right);
            queue_2.push(ptr_2->right);
          } else if (ptr_1->right) {
            ptr_3->right = ptr_1->right;
          } else {
            ptr_3->right = ptr_2->right;
          }
        }
      }
      
      return head;
    }
};