Question 1: expand the binary tree into a linked list
Here is the root node of the binary tree. Please expand it into a single linked list:
The expanded single linked list should also use TreeNode, where the right sub pointer points to the next node in the linked list, and the left sub pointer is always null.
The expanded single linked list should be traversed in the same order as the binary tree.

Example 1:
Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:
Input: root = []
Output: []

Example 3:
Input: root = [0]
Output: [0]

Tips:
The number of nodes in the tree is within the range [0, 2000]
-100 <= Node.val <= 100

Advanced: can you expand this tree using the in place algorithm (O(1) extra space)?

Source: LeetCode
Link: https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list

/**
 * 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:
    void flatten(TreeNode* root) {
        //Idea: first expand the left subtree and right subtree of the node into a linked list, and finally merge the two
        if(root==NULL)
            return;
        //Expand the left subtree first
        flatten(root->left);
        //Then expand the right subtree
        flatten(root->right);
        //At this time, the left and right subtrees have been expanded into a linked list
        
        TreeNode *left=root->left;
        TreeNode *right=root->right;
        //Link the left subtree to the right pointer of the node 
        root->left=NULL;
        root->right=left;
        //Connect the right child number to the end of the tree
        TreeNode *p=root;
        while(p!=NULL&&p->right!=NULL){
            p=p->right;
        }
        p->right=right;
    }
};

Question 2: maximum binary tree
Give an integer array nums without duplicate elements. A maximum binary tree constructed directly and recursively from this array is defined as follows:
The root of the binary tree is the largest element in the array num.
The left subtree is the largest binary tree constructed recursively through the left part of the maximum value in the array.
The right subtree is the largest binary tree constructed recursively through the right part of the maximum value in the array.
Returns the largest binary tree constructed with the given array nums.

Example 1:
Input: num = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]
Explanation: recursive calls are as follows:

• The maximum value in [3,2,1,6,0,5] is 6, the left part is [3,2,1], and the right part is [0,5].
  • The maximum value in [3,2,1] is 3, the left part is [], and the right part is [2,1].
    • Empty array, no child nodes.
    • The maximum value in [2,1] is 2, the left part is [] and the right part is [1].
      • Empty array, no child nodes.
      • There is only one element, so the child node is a node with a value of 1.
  • The maximum value in [0,5] is 5, the left part is [0], and the right part is [].
    • There is only one element, so the child node is a node with a value of 0.
    • Empty array, no child nodes.

Example 2:
Input: num = [3,2,1]
Output: [3,null,2,null,1]

Tips:
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
All integers in nums are different from each other

Source: LeetCode
Link: https://leetcode-cn.com/problems/maximum-binary-tree

/**
 * 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* build(vector<int>& nums,int begin,int end){
        if(begin>end)
            return nullptr;    //nullptr is a null pointer
        int max=0;
        int index=begin;
        for(int i=begin;i<=end;i++){
            if(nums[i]>max){
                max=nums[i];
                index=i;
            }
        }
        TreeNode* root=new TreeNode(max);
        root->left=build(nums,begin,index-1);
        root->right=build(nums,index+1,end);
        return root;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return build(nums,0,nums.size()-1);
    }
};

Question 3: Constructing Binary Trees from traversal sequences in front order and middle order
Given the preorder and inorder of a tree. Please construct a binary tree and return its root node.

Example 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]

Tips:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
Neither preorder nor inorder has duplicate elements
Inorders appear in preorder
Preorder is guaranteed to be the preorder traversal sequence of binary tree
inorder is guaranteed to be a middle order traversal sequence of binary tree

Source: LeetCode
Link: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

/**
 * 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* build(vector<int>& inorder,int inbegin,int inend, vector<int>& preorder,int postbegin,int postend){
        if(inbegin>inend||postbegin>postend)
            return nullptr;
        
        int Val=preorder[postbegin];  //This is the value of the root node
        int index=0;
        for(int i=inbegin;i<=inend;i++){
            if(inorder[i]==Val){
                index=i;
                break;
            }
        }
        
        int leftSize = index - inbegin;
        TreeNode *root = new TreeNode(Val);
        // Recursive construction of left and right subtrees
        root->left = build(inorder, inbegin, index - 1,
                            preorder, postbegin+1, postbegin+leftSize);
        root->right = build(inorder, index + 1, inend,
                            preorder, postbegin + leftSize+1, postend);
        return root;
    }
   
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(inorder,0,inorder.size()-1,preorder,0,preorder.size()-1);
    }
};