669 pruning binary search tree

Given a binary lookup tree and two integers L and R, and l < R, try pruning the binary lookup tree so that the values of all nodes after pruning are within the range of [L, R].

The input is a binary lookup tree and two integers L and R, and the output is a trimmed binary lookup tree.

Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3
Output: [3,2,null,1]

Resolution:

Using the size relationship of binary search tree, we can easily use recursion to process the tree.

Recursively traverse each node. If the current value is greater than high, the trimmed binary tree must appear on the left of the node; If the current value is less than low, the trimmed binary tree appears on the right of the node; If the current node value is within the interval, it recurses to the left and right subtrees.

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(!root){
            return root;
        }
        // If the current value is greater than high, the trimmed binary tree must appear on the left of the node
        if(root->val > high){
            return trimBST(root->left,low,high);
        }
        // If the current value is less than low, the trimmed binary tree appears on the right of the node
        if(root->val < low){
            return trimBST(root->right,low,high);
        }
        // If the current value is within the interval, it recurses to the left and right subtrees
        root->left = trimBST(root->left,low,high);
        root->right = trimBST(root->right,low,high);
        return root;
    }
};

99 restore binary search tree

Given a binary search tree, it is known that two nodes have been accidentally exchanged. Try to restore the tree

The input is a binary search tree with two nodes incorrectly exchanged, and the output is a corrected binary search tree

Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swap 2 and 3 to make the binary search tree valid.

Resolution:

This topic is not understood and needs to be further studied

Using the middle order to traverse a binary search tree, the traversal result is a sequence of increasing node values. Using the characteristics of binary search tree, we can quickly find the wrong nodes.

Get the middle order traversal sequence of the binary search tree, find the wrong node and exchange the values of the two nodes.

class Solution {
public:
    void inorder(TreeNode* root, vector<int>& nums) {
        if (root == nullptr) {
            return;
        }
        inorder(root->left, nums);
        nums.push_back(root->val);
        inorder(root->right, nums);
    }

    pair<int,int> findTwoSwapped(vector<int>& nums) {
        int n = nums.size();
        int index1 = -1, index2 = -1;
        for (int i = 0; i < n - 1; ++i) {
            if (nums[i + 1] < nums[i]) {
                index2 = i + 1;
                if (index1 == -1) {
                    index1 = i;
                } else {
                    break;
                }
            }
        }
        int x = nums[index1], y = nums[index2];
        return {x, y};
    }
    
    void recover(TreeNode* r, int count, int x, int y) {
        if (r != nullptr) {
            if (r->val == x || r->val == y) {
                r->val = r->val == x ? y : x;
                if (--count == 0) {
                    return;
                }
            }
            recover(r->left, count, x, y);
            recover(r->right, count, x, y);
        }
    }

    void recoverTree(TreeNode* root) {
        vector<int> nums;
        inorder(root, nums);
        pair<int,int> swapped= findTwoSwapped(nums);
        recover(root, 2, swapped.first, swapped.second);
    }
};

109 ordered linked list transformation binary search tree

Given a single linked list, the elements are sorted in ascending order and transformed into a highly balanced binary search tree.

Input a linked list and output a balanced binary search tree with a height difference of no more than 1 between the left and right subtrees

Given ordered linked list: [- 10, - 3, 0, 5, 9],

A possible answer is: [0, -3, 9, -10, null, 5], which can represent the following highly balanced binary search tree:

  0
 / \
-3   9
/   /
-10  5

Resolution:

To ensure the balance, we need to find the midpoint of the linked list and construct a binary tree with the midpoint as the root node. The elements less than the midpoint form the left subtree and the elements greater than the midpoint form the right subtree. They correspond to a continuous section in the ordered linked list respectively, which ensures that the difference in the number of nodes between the left and right subtrees does not exceed 1, so as to realize the balance of the binary tree.

After that, using the idea of divide and conquer, we continue to recursively construct the left and right subtrees, find the corresponding midpoint as the root node, and return when the leaf node is constructed.

A common way to find the midpoint of the linked list is the fast and slow pointer. The fast pointer and the slow pointer start at the same node. The fast pointer takes two steps at a time and the slow pointer takes one step at a time. When the fast pointer reaches the end point, the slow pointer points to the midpoint of the linked list. Note the loop condition. In the recursive process of this problem, the next of the last node of the linked list corresponding to the subtree is not necessarily nullptr.

After finding the midpoint of the linked list, construct the node and recursively construct its left and right nodes.

class Solution {
public:

    ListNode* getMid(ListNode* left, ListNode* right){
        ListNode* fast = left;
        ListNode* slow = left;
        // Pay attention to the judgment condition. The termination condition is right-hand connection instead of nullptr
        while(fast != right && fast->next != right){
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }

    TreeNode* buildTree(ListNode* left, ListNode* right){
        if(left == right){
            return nullptr;
        }
        ListNode* midNode = getMid(left,right);
        TreeNode* root = new TreeNode(midNode->val);
        root->left = buildTree(left,midNode);
        root->right = buildTree(midNode->next,right);
        return root;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        // The right boundary of the linked list is nullptr
        return buildTree(head,nullptr);
    }
};

Every time we construct nodes, we need to use fast and slow pointers to traverse the linked list to find the midpoint, which greatly consumes the efficiency of the algorithm. Because the middle order traversal result of the constructed binary search tree is the linked list itself, we can use the middle order traversal idea to reduce the time complexity.

The middle order traversal order is "left subtree - root node - right subtree". In the process of divide and conquer, we don't have to hurry to find the median node of the linked list, but use a placeholder node. When the middle order traverses the node, fill in its value.

In the middle order sequence, if the left endpoint number is left and the right endpoint number is right, then the root node is mid = (left+right+1)/2 or mid = (left+right)/2, the left subtree node range is [left, mid-1], and the right subtree node range is [mid+1, right]. Recover the binary search tree according to the middle order traversal results.

class Solution {
public:
    TreeNode* buildTreeMid(ListNode*& head, int left, int right){
        if(left > right){
            return nullptr;
        }
        int mid = (left+right+1)/2;
        TreeNode* root = new TreeNode();
        root->left = buildTreeMid(head,left,mid-1);
        root->val = head->val;
        head = head->next; // I don't understand why I need to pass references instead of arguments directly
        root->right = buildTreeMid(head,mid+1,right);
        return root;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        int len = 0;
        ListNode* cur = head;
        while(cur){
            ++len;
            cur = cur->next;
        }
        return buildTreeMid(head,0,len-1);
    }
};

450 delete nodes in binary search tree

Given the root node root and a value key of a binary search tree, delete the node corresponding to the key in the binary search tree and ensure that the nature of the binary search tree remains unchanged.

Enter a binary search tree and the node value key to be deleted, and enter a binary search tree after deleting the node key

Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: given that the value of the node to be deleted is 3, we first find 3 and then delete it. A correct answer is [5,4,6,2,null,null,7]

Resolution:

1. Find the node to delete

Using the characteristics of binary search tree, recursively find the nodes to be deleted. If the current node value is less than the key, it will recursively search its right subtree. If the current node value is greater than the key, it will recursively search its left subtree. If it is equal, it will start the deletion operation.

2. Deleted node

To delete a node, there are four situations: the current node is a leaf node, only a left child node, only a right child node, and two child nodes

• The current node is a leaf node: delete the node directly and return NULL as the root node
• The current node has only left child nodes: delete the node, fill in the left child, and return the left child as the root node
• The current node has only the right child node: delete the node, fill in the right child, and return the right child as the root node
• The current node has two child nodes: move the entire left subtree of the current node to the left node of the leftmost node of its right subtree, return to delete the node, and the right node is the new root node

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(!root){
            return root;
        }
        if(root->val == key){
            // Leaf node
            if(!root->left && !root->right){
                delete root;
                return nullptr;
            }
            // Only left node
            else if(root->left && !root->right){
                TreeNode* node = root->left;
                delete root;
                return node;
            }
            // Right node only
            else if(!root->left && root->right){
                TreeNode* node = root->right;
                delete root;
                return node;
            }
            // There are two child nodes
            else{
                TreeNode* cur = root->right;
                while(cur->left){
                    cur = cur->left;
                }
                cur->left = root->left;
                TreeNode* node = root->right;
                delete root;
                return node;
            }
        }
        // Recursively find and delete nodes
        if(root->val > key){
            root->left = deleteNode(root->left,key);
        }
        if(root->val < key){
            root->right = deleteNode(root->right,key);
        }
        return root;
    }
};

reference material

LeetCode 101: easy to brush with you (C + +) Chapter 14 pointer to the tree of three swordsmen