(2022.02.09) 二叉树（labuladong版)

昨天属于是被困难题打击到了，难受。

但是昨天继续左程云加看书，复习二叉树。

今日看左程云，写二叉树，复习二叉树。

//第226题 翻转二叉树
/**
 * 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* invertTree(TreeNode* root) {
        if(root == nullptr){
            return nullptr;
        }
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};


//第116题 填充每个节点的下一个右侧节点
//二叉树的问题难点在于，如何把题目的要求细化成每个节点需要做的事情。
//要充分利用已有的信息，记得思路的转换
class Solution {
public:
    Node* connect(Node* root) {
        if(root == NULL){
            return root;
        }
        connectTwoNode(root->left,root->right);
        return root;
    }
    Node* connectTwoNode(Node* Node1,Node* Node2){
        if(Node1 ==NULL || Node2 == NULL){
            return NULL;
        }
        Node1->next = Node2;
        connectTwoNode(Node1->left,Node1->right);
        connectTwoNode(Node2->left,Node2->right);
        connectTwoNode(Node1->right,Node2->left);
        return NULL;
    }

};

//第114题 二叉树展开为链表
//说不清楚，但是只要知道flatten 的定义如此，相信这个定义，让 root 做它该做的事情，然后 flatten 函数就会按照定义⼯作。(确实，有时候过分抓细节，就会脑抽，我就是典型)
//另外注意递归框架是后序遍历，因为我们要先拉平左右⼦树才能进⾏后续操作。
class Solution {
public:
    void flatten(TreeNode* root) {
        if(root == nullptr || (root->left == nullptr && root->right == nullptr)){
            return;
        }
        flatten(root->left);
        flatten(root->right);

        TreeNode* temp_left = root->left;
        TreeNode* temp_right = root->right;

        root->right = root->left;
        root->left = nullptr;

        TreeNode* p = root;
        while(p->right != nullptr){
            p = p->right;
        }
        p->right = temp_right;
}
};