完成日期：7月20日

总结：

1. auto的使用
2. 注意，判断节点是否为null：①可以直接用节点变量；②但我建议用==nullptr，防止你紧张出错

617. 合并二叉树

//深度优先搜索遍历--递归实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(t1 == nullptr){
            return t2;
        }
        if(t2==nullptr){
            return t1;
        }
        auto merged = new TreeNode(t1->val + t2->val);
        merged->left = mergeTrees(t1->left, t2->left);
        merged->right = mergeTrees(t1->right, t2->right);
        return merged;
    }
};

//广度优先搜索遍历


class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(t1 == nullptr){
            return t2;
        }
        if(t2==nullptr){
            return t1;
        }
        auto merged = new TreeNode(t1->val + t2->val);
        auto q = queue<TreeNode*>();
        auto queue1 = queue<TreeNode*>();
        auto queue2 = queue<TreeNode*>();
        q.push(merged);
        queue1.push(t1);
        queue2.push(t2);
        while(!queue1.empty() && !queue2.empty()){
            auto node = q.front(), node1 = queue1.front(), node2 = queue2.front();
            q.pop();
            queue2.pop();
            queue1.pop();
            auto left1 = node1->left, left2 = node2->left, right1 = node1->right, right2 = node2->right;
            if(left1!=nullptr || left2!=nullptr){
                if(left2!=nullptr&&left1!=nullptr){
                    auto left = new TreeNode(left1->val+left2->val);
                    node->left = left;
                    q.push(left);
                    queue1.push(left1);
                    queue2.push(left2);
                } else if (left1!=nullptr){
                    node->left = left1;
                }else if (left2!=nullptr){
                    node->left = left2;
                }
            }
            if(right1!=nullptr || right2!=nullptr){
                if(right2!=nullptr&&right1!=nullptr){
                    auto right = new TreeNode(right1->val+right2->val);
                    node->right = right;
                    q.push(right);
                    queue1.push(right1);
                    queue2.push(right2);
                } else if (right1!=nullptr){
                    node->right = right1;
                }else if (right2!=nullptr){
                    node->right = right2;
                }
            }
            
        }

        return merged;
    }
};

116. 填充每个节点的下一个右侧节点指针

// 层次遍历（广度优先搜索遍历）
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if(root==nullptr)  return root;
        queue<Node*> q;
        q.push(root);
        while(!q.empty()){
            int size = q.size();
            for(int i = 0; i < size; ++i){
                Node* node = q.front();
                q.pop();
                if(i<size-1){
                    node->next = q.front();
                }
                if(node->left!=nullptr){
                    q.push(node->left);
                }
                if(node->right!=nullptr){
                    q.push(node->right);
                }
            }
        }
        return root;
    }
};

// 直接在原树上操作
class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr)  return root;
        Node* leftmost = root;
        while(leftmost->left){
            Node* head = leftmost;
            while(head){    // 注意，==nullptr和直接用节点的真假
                head->left->next = head->right;
                if(head->next){
                    head->right->next = head->next->left;
                }
                head = head->next;
            }
            leftmost=leftmost->left;
        }
        return root;
    }
};