236. 二叉树的最近公共祖先

543. 二叉树的直径

/**
 * 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:
    int ans=0;
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return ans;
    }
    int dfs(TreeNode *root)
    {
        if(!root)return 0;
        int l=dfs(root->left);//树的直径是根加上左右子树的最大值,枚举每一个树的根,计算其最大值
        int r=dfs(root->right);

        ans=max(ans,l+r);//两结点之间的路径长度是以它们之间边的数目表示
        return max(l,r)+1;
    }
};

124. 二叉树中的最大路径和

 /**
 * 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:
    int ans=-1000000;
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return ans;
    }
    int dfs(TreeNode *root)
    {
        if(!root)return 0;
        int l=dfs(root->left);
        int r=dfs(root->right);
        ans=max(ans,l+r+root->val);
        return max(0,max(l,r)+root->val);
    }
};

112. 路径总和

/**
 * 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:
    bool ans=false;
    bool hasPathSum(TreeNode* root, int targetSum) {
        dfs(root,targetSum,0);
        return ans;
    }
    void dfs(TreeNode* root,int targetSum,int sum)
    {
        if(!root)return;
        if(root->left==NULL&&root->right==NULL&&sum+root->val==targetSum)
        {
            ans=true;
            return ;
        }
        dfs(root->left,targetSum,sum+root->val);
        dfs(root->right,targetSum,sum+root->val);
    }
};

113. 路径总和 II

/**
 * 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:

    vector<int>path;
    vector<vector<int>>ans;
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        dfs(root,targetSum,0);
        return ans;
    }
    void dfs(TreeNode* root,int targetSum,int sum)
    {
        if(!root)return ;
        if(root->left==nullptr&&root->right==nullptr&&sum+root->val==targetSum)
        {
            path.push_back(root->val);
            ans.push_back(path);
            path.pop_back();
            return;
        }
        path.push_back(root->val);
        dfs(root->left,targetSum,sum+root->val);
        dfs(root->right,targetSum,sum+root->val);
        path.pop_back();

    }
};

437. 路径总和 III

/**
 * 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:
    int ans=0;
    unordered_map<int,int>mp;

    int pathSum(TreeNode* root, int targetSum) {
        mp[0]=1;
        dfs(root,targetSum,0);
        return ans;
    }

    void dfs(TreeNode* root,int targetSum,int sum)
    {
        if(!root)return;
        ans+=mp[(sum+root->val)-targetSum];
        mp[root->val+sum]++;
        dfs(root->left,targetSum,sum+root->val);
        dfs(root->right,targetSum,sum+root->val);
        mp[root->val+sum]--;
    }
};

109. 有序链表转换二叉搜索树

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * 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* sortedListToBST(ListNode* head) {
        if(!head)return nullptr;
        int n=0;
        for(auto h=head;h;h=h->next)n++;
        auto root=new TreeNode();
        build(root,head,0,n-1);
        return root;


    }
    void build(TreeNode*& root,ListNode*& head,int l,int r)
    {
        if(l>r)return;
        int mid=l+r>>1;
        root=new TreeNode();

        build(root->left,head,l,mid-1);

        root->val=head->val;
        head=head->next;

        build(root->right,head,mid+1,r);
    }
};

897. 递增顺序搜索树

/**
 * 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* tail;
    TreeNode* increasingBST(TreeNode* root) {
        auto dummy=new TreeNode(-1);
        tail=dummy;
        dfs(root);
        return dummy->right;
    }
    void dfs(TreeNode* root)
    {
        if(!root)return ;
        dfs(root->left);

        tail->right=root,root->left=NULL;
        tail=root;

        dfs(root->right);
    }
};

662. 二叉树最大宽度
题解：
https://www.acwing.com/solution/content/25001/
https://www.acwing.com/solution/content/36988/