Binary tree related problems 2

105. Construction of binary trees from traversal sequences of preorder and middle order

Given two arrays of integers preorder and inorder , among preorder Is the prior traversal of a binary tree , inorder Is the middle order traversal of the same 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]

/**
 * 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 {
    unordered_map<int, int> map;
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i = 0; i < inorder.size(); ++i){
            map[inorder[i]] = i;
        }
        int len = preorder.size();
        return help(preorder, inorder, 0, len - 1, 0, len - 1);
    }

    TreeNode *help(vector<int> &preorder, vector<int> &inorder, int p_left, int p_right, int i_left, int i_right){
        if(p_left > p_right){
            return nullptr;
        }
        // The preamble traverses the position of the root node 
        int p_root = p_left;
        // Traverse the position of the root node in the middle order 
        int i_root = map[preorder[p_root]];
        // Construct the root node 
        TreeNode *root = new TreeNode(inorder[i_root]);
        // Length of left subtree 
        int left_size = i_root - i_left;
        root->left = help(preorder, inorder, p_left + 1, p_root + left_size, i_left, i_root - 1);
        root->right = help(preorder, inorder, p_root + left_size + 1, p_right, i_root + 1, i_right);
        return root;
    }
};

106. Construct binary tree from middle order and post order traversal sequence

Given two arrays of integers inorder and postorder , among inorder Is the middle order traversal of a binary tree , postorder Is the post order traversal of the same tree , Please construct and return this Binary tree .

Example 1:

Input ：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output ：[3,9,20,null,null,15,7]

/**
 * 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 {
    unordered_map<int, int> map;
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        for(int i = 0; i < inorder.size(); ++i){
            map[inorder[i]] = i;
        }
        int len = inorder.size();
        return help(inorder, postorder, 0, len - 1, 0, len - 1);
    }

    TreeNode* help(vector<int> &inorder, vector<int> &postorder, int i_left, int i_right, int p_left, int p_right){
        if(i_left > i_right || p_left > p_right){
            return nullptr;
        }
        int p_root = p_right;
        int i_root = map[postorder[p_root]];
        int left_size = i_root - i_left;
        TreeNode *root = new TreeNode(inorder[i_root]);
        root->left = help(inorder, postorder, i_left, i_root - 1, p_left, p_left + left_size -1);
        root->right = help(inorder, postorder, i_root + 1, i_right, p_left + left_size, p_right - 1);
        return root;
    }
};

654. The largest binary tree

Given an array of non repeating integers nums . The largest binary tree You can use the following algorithm from nums Build... Recursively :

Create a root node , Its value is nums Maximum of .
Recursively at maximum On the left Of Subarray prefix Build the left subtree .
Recursively at maximum On the right Of Subarray suffix Build the right subtree .
return nums Built The largest binary tree .

Example 1：

Input ：nums = [3,2,1,6,0,5]
Output ：[6,3,5,null,2,0,null,null,1]
explain ： The recursive call looks like this ：

• [3,2,1,6,0,5] The maximum value in is 6 , The left part is [3,2,1] , The right part is [0,5] .
  • [3,2,1] The maximum value in is 3 , The left part is [] , The right part is [2,1] .
    • An empty array , No child nodes .
    • [2,1] The maximum value in is 2 , The left part is [] , The right part is [1] .
      • An empty array , No child nodes .
      • There's only one element , So the child node is a value of 1 The node of .
  • [0,5] The maximum value in is 5 , The left part is [0] , The right part is [] .
    • There's only one element , So the child node is a value of 0 The node of .
    • An empty array , No child nodes .

/**
 * 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* constructMaximumBinaryTree(vector<int>& nums) {
        int len = nums.size();
        return help(nums, 0, len);
    }

    TreeNode *help(vector<int> &nums, int left, int right){
        if(left >= right){
            return nullptr;
        }
        int max_value_index = left;
        for(int i = left; i < right; ++i){
            if(nums[i] > nums[max_value_index]){
                max_value_index = i;
            }
        }
        TreeNode *node = new TreeNode(nums[max_value_index]);
        node->left = help(nums, left, max_value_index);
        node->right = help(nums, max_value_index + 1, right);
        return node;
    }
};

617. Merge binary tree

Here are two binary trees ： root1 and root2 .

Imagine , When you cover one tree over the other , Some nodes on the two trees will overlap （ And others don't ）. You need to merge these two trees into a new binary tree . The rule of consolidation is ： If two nodes overlap , Then add the values of the two nodes as the new values of the merged nodes ; otherwise , Not for null The node of will be the node of the new binary tree directly .

Returns the merged binary tree .

Be careful : The merge process must start at the root of both trees .

Example 1：

Input ：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output ：[3,4,5,5,4,null,7]

/**
 * 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* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1 == nullptr){
            return root2;
        }
        if(root2 == nullptr){
            return root1;
        }
        root1->val += root2->val;
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);
        return root1;
    }
};

700. Search in binary search tree

Given a binary search tree （BST） The root node root And an integer value val.

You need to BST The node value found in is equal to val The node of . Return the subtree with this node as the root . If the node doesn't exist , Then return to null .

Example 1:

Input ：root = [4,2,7,1,3], val = 2
Output ：[2,1,3]

/**
 * 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 {
    TreeNode *node = new TreeNode;
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root == nullptr){
            return root;
        }
        if(root->val == val){
            return root;
        }
        if(root->val > val){
            return searchBST(root->left, val);
        } else if(root->val < val){
            return searchBST(root->right, val);
        }
        return nullptr;
    }
};

98. Verify binary search tree

Give you the root node of a binary tree root , Determine whether it is an effective binary search tree .

It works The binary search tree is defined as follows ：

The left subtree of the node contains only Less than Number of current nodes .
The right subtree of the node contains only Greater than Number of current nodes .
All left and right subtrees themselves must also be binary search trees .

Example 1：

Input ：root = [2,1,3]
Output ：true

/**
 * 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 {
    vector<int> res;
public:
    bool isValidBST(TreeNode* root) {
        help(root);
        for(int i = 0; i < res.size() - 1; ++i){
            if(res[i] >= res[i + 1]){
                return false;
            }
        }
        return true;
    }

    void help(TreeNode *root){
        if(!root){
            return;
        }
        help(root->left);
        res.push_back(root->val);
        help(root->right);
        return;
    }
};

530. The minimum absolute difference of binary search tree

Give you a binary search tree root node root , return The minimum difference between the values of any two different nodes in the tree .

The difference is a positive number , Its value is equal to the absolute value of the difference between the two values .

Example 1：

Input ：root = [4,2,6,1,3]
Output ：1

/**
 * 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 {
    vector<int> res;
public:
    int getMinimumDifference(TreeNode* root) {
        help(root);
        int _min = INT_MAX;
        for(int i = 0; i < res.size() - 1; ++i){
            if(res[i + 1] - res[i] < _min){
                _min = res[i + 1] - res[i];
            }
        }
        return _min;
    }

    void help(TreeNode *root){
        if(root == nullptr){
            return;
        }
        help(root->left);
        res.push_back(root->val);
        help(root->right);
    }
};

501. The mode in the binary search tree

Give you a binary search tree with duplicate values （BST） The root node root , Find out and return to BST All in The number of （ namely , The most frequent element ）.

If there is more than one mode in the tree , Can press In any order return .

Assume BST Meet the following definitions ：

The value of the node contained in the left subtree of the node Less than or equal to The value of the current node
The value of the node contained in the right subtree of the node Greater than or equal to The value of the current node
Both the left and right subtrees are binary search trees

Example 1：

Input ：root = [1,null,2,2]
Output ：[2]

/**
 * 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 {
    unordered_map<int, int> map;
public:

    bool static cmp(const pair<int, int> &a, const pair<int, int> &b){
        return a.second > b.second;
    }
    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        help(root, res);
        // for(auto it = map.begin())
        vector<pair<int, int>> vec(map.begin(), map.end());
        sort(vec.begin(), vec.end(), cmp);
        res.push_back(vec[0].first);
        for(int i = 1; i < vec.size(); ++i){
            if(vec[i].second == vec[0].second){
                res.push_back(vec[i].first);
            }
        }
        return res;
    }

    void help(TreeNode *root, vector<int> &res){
        if(root == nullptr){
            return;
        }
        help(root->left, res);
        // res.push_back(root->val);
        map[root->val]++;
        help(root->right, res);
    }
};

236. The nearest common ancestor of a binary tree

Given a binary tree , Find the nearest common ancestor of the two specified nodes in the tree .

In Baidu Encyclopedia, the most recent definition of public ancestor is ：“ For a tree T Two nodes of p、q, The nearest common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible （ A node can also be its own ancestor ）.”

Example 1：

Input ：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output ：3
explain ： node 5 And nodes 1 The most recent public ancestor of is the node 3 .

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // If you find p Node or q The node returns 
        if(root == q || root == p || root == NULL){
            return root;
        }
        
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);

        if(left != NULL && right != NULL){
            return root;
        }
        if(left == NULL && right != NULL){
            return right;
        } else if(left != NULL && right == NULL){
            return left;
        } else {
            return NULL;
        }
    }
};

235. The nearest common ancestor of a binary search tree

Given a binary search tree , Find the nearest common ancestor of the two specified nodes in the tree .

In Baidu Encyclopedia, the most recent definition of public ancestor is ：“ For a tree T Two nodes of p、q, Recently, the common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible （ A node can also be its own ancestor ）.”

for example , Given the following binary search tree : root = [6,2,8,0,4,7,9,null,null,3,5]

Example 1:

Input : root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output : 6
explain : node 2 And nodes 8 The most recent public ancestor of 6.
Example 2:

Input : root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output : 2
explain : node 2 And nodes 4 The most recent public ancestor of 2, Because by definition, the nearest common ancestor node can be the node itself .

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == p || root == q || root == NULL){
            return root;
        }
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if(left != NULL && right != NULL){
            return root;
        }
        if(left == NULL && right != NULL){
            return right;
        } else if(left != NULL && right == NULL){
            return left;
        } else {
            return NULL;
        }
    }
};

701. Insert operation in binary search tree

Given a binary search tree （BST） The root node root And the value to be inserted into the tree value , Insert values into a binary search tree . Return to the root node of the binary search tree after insertion . input data Guarantee , The new value is different from any node value in the original binary search tree .

Be careful , There may be many effective insertion methods , As long as the tree remains a binary search tree after insertion . You can go back to Any valid result .

Example 1：

Input ：root = [4,2,7,1,3], val = 5
Output ：[4,2,7,1,3,5]
explain ： Another tree that meets the requirements of the topic is ：

/**
 * 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* insertIntoBST(TreeNode* root, int val) {
        if(root == nullptr){
            TreeNode *node = new TreeNode(val);
            return node;
        }
        if(val < root->val){
            root->left = insertIntoBST(root->left, val);
        }
        if(val > root->val){
            root->right = insertIntoBST(root->right, val);
        }
        
        return root;
    }
};