Common interview questions of binary tree

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using std::cout;
using std::cin;

  struct TreeNode {
    
        int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {
    }
 };
// subject 1. The successor 
// Design an algorithm , Find the... Of the specified node in the binary search tree “ next ” node （ That is to say, the middle order follows ).
class Solution1 {
    
public:
    void Tree(TreeNode* root, TreeNode** ret, int* n)
    {
    
        if (root == nullptr)
        {
    
            return;
        }
        Tree(root->left, ret, n);
        ret[(*n)++] = root;
        Tree(root->right, ret, n);
    }
    int TreeSize(TreeNode* root)
    {
    
        if (root == nullptr)
        {
    
            return 0;
        }
        int leftSize = TreeSize(root->left);
        int rightSize = TreeSize(root->right);
        int sum = leftSize + rightSize + 1;
        return sum;
    }
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
    
        int Size = TreeSize(root);// Calculate the binary tree size 
        TreeNode** ret = new TreeNode * [Size];
        int n = 0;
        Tree(root, ret, &n);
        TreeNode* next = NULL;
        for (int i = 0; i < n; i++)
        {
    
            if (ret[i] == p && i < n - 1)
            {
    
                next = ret[i + 1];
            }
        }
        return next;
    }
};
// Tree form DP Routine pithy formula 
//(1) Suppose X The node is the head , Suppose you can ask X Left tree and X The right tree wants any information 
//(2) Under the assumptions of the previous step , Discuss with X A tree that is a head node , The possibility of getting the answer ( above all )
//(3) After listing all the possibilities , Determine what kind of information you need from the left tree and the right tree 
//(4) Find the complete set of left tree information and right tree information , Is the information that any subtree needs to return S
//(5) Recursive functions return S, Every sub tree asks so 

// subject 2. Balanced binary trees 
// Given a binary tree , Determine if it's a highly balanced binary tree .
// In this question , A height balanced binary tree is defined as ：
// Every node of a binary tree   The absolute value of the height difference between the left and right subtrees is not more than  1.
int maxDepth(struct TreeNode* root) {
    
    if (root == NULL)
    {
    
        return 0;
    }
    int treeleft = maxDepth(root->left);
    int treeright = maxDepth(root->right);
    return treeleft > treeright ? treeleft + 1 : treeright + 1;
}
bool isBalanced(struct TreeNode* root) {
    
    if (root == NULL)
    {
    
        return true;
    }
    int treeleft = maxDepth(root->left);// Determine whether the left tree is a balanced binary tree 
    int treeright = maxDepth(root->right);// Determine whether the right tree is a binary tree 
    return abs(treeleft - treeright) < 2 && isBalanced(root->left) && isBalanced(root->right);
}
// subject 3. The longest distance between nodes in the tree 
// Given the head node of a binary tree head, There is a distance between any two nodes , Given the head node of a binary tree head, There is a distance between any two nodes 
// Returns the maximum distance of the entire binary tree 
struct Info3
{
    
    int MaxDistance;// Record the maximum distance in the node 
    int height;
    Info3(int a, int b)
    {
    
        MaxDistance = a;
        height = b;
    }
};
class Solution3 {
    
public:
   
    Info3* Process3(TreeNode* head)
    {
    
        if (head == nullptr)
        {
    
            return new Info3(0, 0);
        }
        Info3* left = Process3(head->left);
        Info3* right = Process3(head->right);
        int height = fmax(left->MaxDistance, right->MaxDistance) + 1;
        int Distance = fmax(left->height + right->height + 1, fmax(left->MaxDistance, right->MaxDistance));
        delete left;
        delete right;
        return new Info3(Distance, height);
     }
    int MaxDistance(TreeNode* head)// The main function 
    {
    
        return Process3(head)->MaxDistance;
    }
};
// subject 4. Maximum binary search 
// Given the head node of a binary tree head,
// Returns the number of nodes of the largest binary search subtree in the binary tree 
struct Info4
{
    
    bool isALLBST;// Whether it is a binary search tree 
    int max;// Record the maximum nodes 
    int min;// Record minimum node 
    int Sum;// The maximum number of nodes in the binary search tree 
    Info4(bool s, int _max, int _min, int _Sum)
    {
    
        isALLBST = s;
        max = _max;
        min = _min;
        Sum = _Sum;
      
    }
};
class Solution4
{
    
public:
    Info4* Process4(TreeNode* head)
    {
    
        if (head == nullptr)
        {
    
            return nullptr;
        }
        Info4* left = Process4(head->left);
        Info4* right = Process4(head->right);
        int max = head->val;
        int min = head->val;
        if (left != nullptr)
        {
    
            max = fmax(max, left->max);
            min = fmin(min, right->min);
        }
        if (right != nullptr)
        {
    
            max = fmax(max, right->max);
            min = fmin(min, right->min);
        }
        bool s = false;// The default is not binary search prime tree 
        int sum = 0;
        if (left != nullptr)
        {
    
            sum = left->Sum;
        }
        if (right != nullptr)
        {
    
            sum = right->Sum;
        }
        if (left == nullptr ? true : (left->isALLBST)
            && right == nullptr ? true : (right->isALLBST) 
            && left == nullptr ? true : (left->max<head->val)
            && right == nullptr ? true : (right->min>head->val)
            )
        {
    
            s = true;
            sum = (left == nullptr ? 0 : left->Sum) + (right == nullptr ? 0 : right->Sum) + 1;
           
        }
        delete left;
        delete right;
        return new Info4(s, max, min, sum);
    }
    int MaxBstSize(TreeNode* head)
    {
    
        return Process4(head)->Sum;
    }
};
// subject 5. Judging the full binary tree 
// The head node of a given number , Returns whether the tree is full of binary trees 
// skill : The full binary tree conforms to 2^ Height -1 =  Number of nodes 
struct Info5
{
    
    int height;// Record the height of the tree 
    int Sum;// Record the number of nodes 
    Info5(int _height, int _Sum)
    {
    
        height = _height;
        Sum = _Sum;
    }
};
class Solution5
{
    
public:
   Info5* Process5(TreeNode* head)
    {
    
       if (head == nullptr)
       {
    
           return new Info5(0, 0);
       }
       Info5* left = Process5(head->left);
       Info5* right = Process5(head->right);
       int height = fmax(left->height, right->height) + 1;
       int Sum = left->Sum + right->Sum + 1;
       delete left;
       delete right;
       return new Info5(height, Sum);
       }
   bool IsAllTree(TreeNode* head)
   {
    
       Info5* s = Process5(head);
       bool f = pow(2, s->height) == s->Sum;
       delete s;
       return f;
   }
};