今天的主题还是搜索~

冲，冲，冲！

617. Merge Two Binary Trees

Analysis

果然，简单题都很直接，不会做完全就是基础不够扎实...

Code

dfs

/* dfs */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1 == nullptr) return root2;
        if(root2 == nullptr) return root1;
        TreeNode* merged_node = new TreeNode(root1->val + root2->val);
        merged_node->left = mergeTrees(root1->left, root2->left);
        merged_node->right = mergeTrees(root1->right, root2->right);
        return merged_node;
    }
};

用 dfs 写是真的简单。

bfs

/* bfs */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1 == nullptr) return root2;
        if(root2 == nullptr) return root1;
        TreeNode* merged_node = new TreeNode(root1->val + root2->val);
        queue<TreeNode*> q, q1, q2;
        q.push(merged_node);
        q1.push(root1);
        q2.push(root2);
        while(!q1.empty() && !q2.empty()) {
            auto node = q.front(), node1 = q1.front(), node2 = q2.front();
            q.pop(), q1.pop(), q2.pop();
            auto left1 = node1->left, left2 = node2->left;
            auto right1 = node1->right, right2 = node2->right;
            if(left1 != nullptr || left2 != nullptr) {
                if(left1 != nullptr && left2 != nullptr) {
                    auto left = new TreeNode(left1->val + left2->val);
                    node->left = left;
                    q.push(left);
                    q1.push(left1);
                    q2.push(left2);
                } else if(left1 != nullptr) {
                    node->left = left1;
                } else if(left2 != nullptr) {
                    node->left = left2;
                }
            }
            if(right1 != nullptr || right2 != nullptr) {
                if(right1 != nullptr && right2 != nullptr) {
                    auto right = new TreeNode(right1->val + right2->val);
                    node->right = right;
                    q.push(right);
                    q1.push(right1);
                    q2.push(right2);
                } else if(right1 != nullptr) {
                    node->right = right1;
                } else if(right2 != nullptr) {
                    node->right = right2;
                }
            }
        }
        return merged_node;
    }
};

用 bfs 写真的麻烦了很多，而且就代码的执行效率和消耗空间而言，也不太优秀。
很久没有写跟树相关的代码了，反而不太会了。

116. Populating Next Right Pointers in Each Node

Analysis

又是跟树相关的题目，因为没有复习树的相关知识点，感觉练习的效果不是很好。
扯远了，回到这道题。读完题目，这个题一看就想到用层序遍历（bfs），但是需要解决的问题是如何判断那些结点是在同一层。应该可以从结点个数下手，因为题目已经限定了是完美二叉树。

Code

level order

/* level order */
class Solution {
public:
    Node* connect(Node* root) {
        if(root == nullptr) return nullptr;
        queue<Node*> q;
        int cnt = 1;
        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;
    }
};

好吧，真是生疏了，并不用判断是不是在一层，因为层序遍历就是一层一层遍历的，看来是完全忘记树的层序遍历了😂。不过，虽然可以用层序遍历解决这个问题，但是题目要求使用常数个存储空间，也就是空间复杂度得是$O(1)$，那只能换一种方法来做了。

next pointer

仔细想一想，题目要做的事情实际上就是将树的每一层结点串起来形成一个链表，这样要做的事情就是找到指定结点的地址并交给对应的 next。当位于第 N 层时，可以很容易的找到第 N + 1 层的结点，因为父节点可以很容易找到子结点。这时，就存在 2 种情况：

子结点的父节点相同，这样左子结点的 next 就有：leftchild->next = parent->right。
子结点的父节点不同，也就是右子结点与另一颗父节点的左子结点相连，也就有：rightchild->next = parent->next->left。

有了这个思路后还需要考虑一下根节点跟每一层的最后一个结点。根节点直接修改 next 就可以了，但是如何知道是最后一个结点呢？实际上在第 N 层时，这一层的链表已经在第 N - 1 层构造好了，也就是说，直接遍历即可，到末尾自然就是 NULL 了。
另外，将根结点当作第 0 层，可能会好理解一些。

/* use next pointer */
class Solution {
public:
    Node* connect(Node* root) {
        if(root == nullptr) return nullptr;
        Node* leftmost = root;
        while(leftmost->left != nullptr) {
            Node* head = leftmost;
            while(head != nullptr) {
                head->left->next = head->right;
                if(head->next != nullptr) head->right->next = head->next->left;
                head = head->next;
            }
            leftmost = leftmost->left;
        }
        return root;
    }
};

Summary

看着今天的主题还是搜索以为还是简单的纯搜索问题呢，没想到直接跟树联系到一起了...嗯，明天不会直接就上图了吧？
这两道题也是很基础常规的与树相关的题目，没做出来，真该反省一下了。