235. Nearest common ancestor of a binary search tree
Given a binary search tree, find the nearest common ancestor of two specified nodes in the tree.
The definition of nearest common ancestor in Baidu's encyclopedia is: "For two nodes p, q of a rooted tree T, the nearest common ancestor is denoted as a node x that satisfies that x is an ancestor of p, q and that the depth of x is as large as possible (a node can also be an ancestor of itself)."
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
Explanation: The nearest common ancestor of node 2 and node 8 is 6.
Example 2.
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The nearest common ancestor of node 2 and node 4 is 2, because by definition the nearest common ancestor can be the node itself.
Description.
The values of all nodes are unique.
p, q are distinct nodes and both exist in the given binary search tree.
correct solution (a math. equation)
Searching from the bottom up using backtracking, a node is encountered with p in its left subtree and q in its right subtree, then the current node is the nearest common ancestor.
So this question is about binary search trees, which are ordered, so you have to take advantage of that.
In an ordered tree, what if you determine that a node has p in its left subtree and q in its right subtree?
Since it is an ordered tree, if the middle node is a common ancestor of q and p, then the array of middle nodes must be in the interval [p, q].
i.e., middle node > p && middle node < q or middle node > q && middle node < p.
Then by traversing from top to bottom and encountering a cur node that is numerically in the interval [p, q] it must follow that the node cur is the common ancestor of p and q.
- Determining the return value of a recursive function and its parameters
The arguments are the current node, and the two nodes p, q.
The return value is to return the nearest common ancestor, so it's TreeNode *. - Determination of termination conditions
Just return to empty
It doesn't even need to be a termination condition.
Because the title says that p and q are distinct nodes and both exist in the given binary search tree.
This means that the common ancestor will definitely be found, so there is no such thing as encountering a null. - Determining the logic of single-level recursion
When traversing a binary search tree is to find the interval [p->val, q->val] (note that it is left-closed and closed here)
Then if cur->val is greater than p->val and also cur->val is greater than q->val, then it should be traversed to the left (indicating that the target interval is in the left subtree).
Note that at this point it is not known who is bigger, p or q, so both are judged
Upcode (●'◡'●)
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root->val > p->val && root->val > q->val) {
return lowestCommonAncestor(root->left, p, q);
} else if (root->val < p->val && root->val < q->val) {
return lowestCommonAncestor(root->right, p, q);
} else return root;
}
};
701. Insertion operations in binary search trees
Given the root node root of a binary search tree (BST) and the value value to be inserted into the tree, insert the value into the binary search tree. Return the root node of the binary search tree after insertion. The input data guarantees that the new value is different from the value of any node in the original binary search tree.
Note that there may be multiple valid insertions, as long as the tree remains a binary search tree after the insertion. You can return any valid result.
Example 1:
Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: another tree that meets the requirements of the topic to pass is:
Example 2:
Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]
Example 3:
Input: root = [4,2,7,1,3,null,null,null,null,null], val = 5
Output: [4,2,7,1,3,5]
Tip:
The number of nodes in the tree will be in [0, 104] within the scope of the
-108 <= <= 108
All values are unique.
-108 <= val <= 108
Ensure that val does not exist in the original BST.
correct solution (a math. equation)
This is actually an easy question, but the hints in the question:
There are a variety of valid insertion methods and the ability to reconstruct a binary search tree, which immediately scared off a lot of people and instantly made the topic feel a lot more complex.
In fact, you can disregard the insertion method that changes the structure of the tree as stated in the question's hint.
As you can see in the demo video below: just follow the rules for traversing a binary search tree and insert nodes when you encounter empty nodes.
For example, to insert element 10, you need to find the end node and insert it.
The same reasoning goes for inserting element 15, inserting element 0, inserting element 6; the
Do I need to adjust the structure of the binary tree? Not really.
Just traverse the binary search tree, find the empty node and insert the element, then the problem is actually simple.
The next step is to traverse the binary search tree
- Determining recursive function parameters and return values
The parameters are the root node pointer, and the element to be inserted, should the recursive function have a return value here?
May or may not be available.
But recursive functions are tricky to implement if they don't have a return value; the
If there is a return value, you can use the return value to complete the assignment of the newly added node to its parent. (explained further below)
The return type of the recursive function is the node type TreeNode * . - Determination of termination conditions
The termination condition is to find the traversed node is null is the location of the node to be inserted, and return the inserted node.
Here returning the added node to the previous layer completes the parent-child node assignment operation - Determining the logic of single-level recursion
At this point it should be clear, do you need to traverse the whole tree?
Don't forget that this is a search tree, and traversing the entire search tree is simply an insult to the search tree.
The search tree is oriented, and the recursive direction can be determined based on the value of the inserted element.
Upper code (●'◡'●)
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == NULL) {
TreeNode* node = new TreeNode(val);
return node;
}
if (root->val > val) root->left = insertIntoBST(root->left, val);
if (root->val < val) root->right = insertIntoBST(root->right, val);
return root;
}
};
450. Deleting nodes in a binary search tree
Given a binary search tree with a root node and a value key, delete the node corresponding to key in the binary search tree and ensure that the nature of the binary search tree remains unchanged. Returns a reference to the root node of the binary search tree (which may be updated).
In general, deleting a node can be done in two steps:
First find the node that needs to be deleted;
If you find it, delete it.
Example 1.
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 the node 3 and then delete it.
A correct answer is [5,4,6,2,null,null,7], as shown below.
Another correct answer is [5,2,6,null,4,null,7].
Example 2.
Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: A binary tree does not contain nodes with value 0.
Example 3.
Input: root = [], key = 0
Output: []
Tip.
Range of the number of nodes [0, 104].
-105 <= <= 105
Node values are unique
root is a legal binary search tree.
-105 <= key <= 105
Advanced: Requires the algorithm to have a time complexity of O(h), with h being the height of the tree.
correct solution (a math. equation)
Node deletion in a search tree is much more complex than node addition, and there are many scenarios to consider
- Determining recursive function parameters and return values
Here nodes can be deleted by recursively returning values. - Determination of termination conditions
Encountered empty return, in fact, this also indicates that did not find the deleted node, traversing to the empty node directly return the - Determining the logic of single-level recursion
Here's where the situations encountered with deleting nodes in a binary search tree are figured out.
There are five of them:
- The first case: did not find the deleted node, traversing to the empty node directly returned the
- Second case: left and right children are empty (leaf nodes), directly delete the node, return NULL for the root node
- Third case: the left child of the deleted node is empty, the right child is not empty, the node is deleted, the right child is complemented and the right child is returned as the root node
- Fourth case: the right child of the deleted node is empty, the left child is not empty, the node is deleted, the left child is complementary, and the left child is returned as the root node
- The fifth case: the left and right child nodes are not empty, then the left subtree head node (left child) of the deleted node is placed on the left child of the leftmost node of the right subtree of the deleted node, and the right child of the deleted node is returned as the new root node.
Upcode (●'◡'●)
class Solution {
public.
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return root; // First case: no deleted node found, traversing to null node returns it directly
if (root->val == key) {
// Second case: both left and right children are null (leaf nodes), delete the node and return NULL as the root node.
if (root->left == nullptr && root->right == nullptr) {
///! Memory release
delete root; return nullptr; return nullptr; ///!
return nullptr.
}
// Third case: left child is null, right child is not null, delete node, right child is complementary, return right child as root.
else if (root->left == nullptr) {
auto retNode = root->right;
///! Memory release
delete root; return retNode; ///!
return retNode; }
}
// Fourth case: right child is null, left child is not null, delete node, left child is filled in, return left child to root
else if (root->right == nullptr) {
auto retNode = root->left;
///! Memory release
delete root; return retNode; ///!
return retNode; }
}
// In the fifth case, where neither the left nor the right child is empty, the left child of the deleted node is placed in the left child of the leftmost node of the deleted node's right child
// and return the right child of the deleted node as the new root node.
else {
TreeNode* cur = root->right; // Find the leftmost node of the right subtree
while(cur->left ! = nullptr) {
cur = cur->left;
}
cur->left = root->left; // place the left subtree of the node to be deleted (root) in the position of cur's left child
TreeNode* tmp = root; // Save the root node for deletion below.
root = root->right; // return the right child of the old root as the new root
delete tmp; // free node memory (it's fine to leave it out here, but C++ is better off freeing it manually)
return root; }
}
}
if (root->val > key) root->left = deleteNode(root->left, key);
if (root->val < key) root->right = deleteNode(root->right, key); } } if (root->val < key)
return root; }
}
};
It's not easy to write a blog, so please give me some support 8~!