【Leetcode】二叉树刷题I：226/116/114

还是喜欢手写笔记，这里就直接附上笔记图片和代码（Cpp）。

学习资源：公众号labuladong

一、二叉树总述：

二、leetcode226:

/**
 * 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==NULL) return NULL;
        //先对根节点进行交换。
        TreeNode* tmp = root->left;
        root->left=root->right;
        root->right=tmp;
        //再对左右子树分别遍历。
        invertTree(root->left);
        invertTree(root->right);

        return root;
    }
};

三、leetcode116:

/*
// 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==NULL) return NULL;
        connectNode(root->left,root->right);
        return root;
    }

    void connectNode(Node* node1,Node* node2){
        if(node1==NULL || node2==NULL) return;
        //前序遍历：
        node1->next = node2;
        connectNode(node1->left,node1->right);
        connectNode(node2->left,node2->right);
        connectNode(node1->right,node2->left);
    }
};

四、Leetcode114: 

/*  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) {}
  };
 */
 #include <stdio.h>
 #include <iostream>
 using namespace std;
class Solution {
public:
    void flatten(TreeNode* root) {
        if(root == NULL) return;

        //把左右子树分别展开。
        flatten(root->left);
        flatten(root->right);

        //让左子树成为右子树。
        TreeNode* left = root->left;
        TreeNode* right= root->right;
        root->left = NULL;
        root->right = left;

        TreeNode* p = root;  //让p存根。
        while(p->right != NULL){
            p = p->right;  //让此时的右子树，即最初的左子树，当作p。
        }
        p->right = right;   //把最初的右子树连到现在的右子树的右子树处。

    }
};

 五、感悟：

• 相信“定义”——从框架看问题，关注点不要放在细节上。
• 搞清root该做的事情。
•  二叉树的关键，是把题目要求细化成每个节点该做的事情。