完成日期：7月20日

總結(jié)：

1. auto的使用
2. 注意，判斷節(jié)點是否為null：①可以直接用節(jié)點變量；②但我建議用==nullptr，防止你緊張出錯

617. 合并二叉樹

//深度優(yōu)先搜索遍歷--遞歸實現(xiàn)

/**
 * 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;
    }
};

//廣度優(yōu)先搜索遍歷


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. 填充每個節(jié)點的下一個右側(cè)節(jié)點指針

// 層次遍歷（廣度優(yōu)先搜索遍歷）
/*
// 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和直接用節(jié)點的真假
                head->left->next = head->right;
                if(head->next){
                    head->right->next = head->next->left;
                }
                head = head->next;
            }
            leftmost=leftmost->left;
        }
        return root;
    }
};