This paper introduces the thinking and solving method of a binary tree recursion problem.
When thinking about recursion problems like this, focus on what the layer node is trying to accomplish and what data the child node needs to provide (the return value of the recursive function) and what data the parent node needs to pass (the parameters of the recursive function) to accomplish that task.
There is no need to think about how the child node does its job, just assume that the child node has done its job and is able to provide key data for its own use (this is particularly obvious in the following section on tree reconstruction based on middle and pre-order traversal and tree link list, there is no need to think about how the child node does its job). Finally, the layer node also returns its own processing results to the parent node and passes the parameters needed by the child node.
Below use this idea to solve from easy to difficult to solve some problems.
Only the child node returns the information to the parent node
The height of a binary tree
LeetCode the original leetcode-cn.com/problems/ma…
- Topic describes
Given a binary tree, find its maximum depth. The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node. Note: Leaf nodes are nodes that have no child nodes.Copy the code- Answer key
They want the height of the tree, and each node has its own height. The height of the parent node is determined by the height of the parent node and its sibling node.
- Define each level of tasks and how to drive recursion
For each node, the height of the subtree is counted and the height of the layer is calculated. And returns the height information to the parent node. Recursion down the tree drives recursion.
- Determine what results the child node needs to return and what information the parent node needs to send in order to complete this layer’s tasks.
To calculate the height of the subtree of the book, we only need to know the height of the left and right subtrees and calculate Max plus 1. Therefore, we need the child node to return the height information of the subtree. No information is required from the parent node.
- Specify the termination conditions and the final question
If the node is null, return 0. There is no need to determine whether the node is a leaf, which will result in too many judgment statements. They’re essentially asking for the height of the root node.
- AC code
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == nullptr)
return 0;
return std::max(maxDepth(root->left), maxDepth(root->right)) + 1; }};Copy the codeDetermines whether the tree is a balanced binary tree
Leetcode the original leetcode-cn.com/problems/ba…
- Topic describes
Given a binary tree, determine whether it is a highly balanced binary tree. In this case, a highly balanced binary tree is defined as: the absolute value of the height difference between the left and right subtrees of each node of a binary tree is no more than 1Copy the code- Answer key
According to the definition of balanced binary tree, each node must meet the balance condition, that is, it needs to know the height information of its left and right subtrees.
- Define each level of tasks and how to drive recursion
For each node, the height of the subtree is counted and the height of the layer is calculated. And returns the height information to the parent node. Recursion down the tree drives recursion.
- Is it clear what results the child node needs to return and what information the parent node needs to send in order to complete the tasks of this layer
To calculate the height of the subtree of the book, it is necessary to know the height of the left and right subtrees and calculate Max plus 1. Therefore, the child node is required to return the height information of the subtree. Since it is possible that a descendant node does not meet the definition of balanced binary tree, the whole tree does not meet the condition. Therefore, descendant nodes are required to return the definition information of balanced binary tree. No information is required from the parent node.
- Specify the termination conditions and the final question
If the node is null, return 0 without checking whether the node is a leaf. So they want to know if the root of the tree satisfies the condition for a balanced binary tree.
- AC code
According to the above analysis, combined with pruning, the code can be obtained as follows:
class Solution {
public:
bool isBalanced(TreeNode* root) {
auto ret = dfs(root);
return ret.second;
}
// From the above analysis, we can see that the return value of the recursive function should contain two information: 1. Height of subtree; 2. Whether the subtree meets the condition of balanced binary tree.
std::pair<int.bool> dfs(TreeNode *root)
{
if(root == nullptr) {return std::make_pair(0.true);
}
auto left_ret = dfs(root->left);
if(! left_ret.second){return std::make_pair(0.false);
}
auto right_ret = dfs(root->right);
if(! right_ret.second){return std::make_pair(0.false);
}
if(std::abs(left_ret.first - right_ret.first) > 1) {return std::make_pair(0.false);
}
//+1 is the node of this layer
return std::make_pair(std::max(left_ret.first, right_ret.first)+1.true); }};Copy the codeVerify the binary search tree
Leetcode the original leetcode-cn.com/problems/va…
- Topic describes
You are given the root node of a binary tree to determine whether it is a valid binary search tree.Copy the code- Answer key
The problem is similar to checking whether the tree is a balanced binary tree. According to the definition of binary search tree, each node needs to meet the definition of binary search, that is, each node needs to know the maximum and minimum values of the left and right subtrees. And then make a judgment based on that.
- Define each level of tasks and how to drive recursion
For each node, the maximum and minimum values of the left and right subtrees are obtained, and the value of this node is compared with the maximum values of the left and right subtrees to determine whether the definition of binary search tree is satisfied. Finally returns the maximum and minimum values of the subtree. And returns the height information to the parent node. Recursion down the tree drives recursion.
- Is it clear what results the child node needs to return and what information the parent node needs to send in order to complete the tasks of this layer
It is necessary to know the maximum and minimum values of the left and right subtrees to judge whether the subtree meets the conditions of binary search tree, so the child node needs to return the maximum value of the subtree. Because some descendant node may not meet the definition of binary search tree, the whole tree does not meet the conditions. Therefore, the descendant nodes need to return the definition information of whether the binary search tree is satisfied. No information is required from the parent node.
- Specify the termination conditions and the final question
A leaf returns itself and terminates recursion, and recursion continues in other cases. So they want to know if the root of the tree meets the criteria for searching binary trees
- AC code
class Solution {
public:
bool isValidBST(TreeNode* root) {
if(root == nullptr)
return true;
auto tp = isValidBSTCore(root);
return std::get<2>(tp);
}
// Minimum value, maximum value, ok
std::tuple<int.int.bool> isValidBSTCore(TreeNode *root)
{
if(root->left ! =nullptr&& root->right ! =nullptr)
{
auto left_tp = isValidBSTCore(root->left);
auto right_tp = isValidBSTCore(root->right);
// The subtree has a problem
if(std::get<2>(left_tp) == false || std::get<2>(right_tp) == false)
return std::make_tuple(0.0.false);
// The maximum value of the left subtree is greater than root or the minimum value of the right subtree is less than root
if(std::get<1>(left_tp) >= root->val || std::get<0>(right_tp) <= root->val)
return std::make_tuple(0.0.false);
else
return std::make_tuple(std::get<0>(left_tp), std::get<1>(right_tp), true);
}
else if(root->left ! =nullptr)
{
auto left_tp = isValidBSTCore(root->left);
if(std::get<2>(left_tp) == false || std::get<1>(left_tp) >= root->val)
return std::make_tuple(0.0.false);
else
return std::make_tuple(std::get<0>(left_tp), root->val, true);
}
else if(root->right ! =nullptr)
{
auto right_tp = isValidBSTCore(root->right);
if(std::get<2>(right_tp) == false || std::get<0>(right_tp) <= root->val)
return std::make_tuple(0.0.false);
else
return std::make_tuple(root->val, std::get<1>(right_tp), true);
}
else
{
return std::make_tuple(root->val, root->val, true); }}};Copy the codeHouse robbery III
Leetcode the original leetcode-cn.com/problems/ho…
- Topic describes
After robbing a street and a circle of houses, the thieves found a new area to burgle. There is only one entrance to this area, which we call the Root. In addition to the root, each house has one and only one parent house attached to it. After some sleuthing, the clever thief realized that "all the houses in this place are arranged like a binary tree." If two directly connected houses are robbed on the same night, the house will automatically alarm the police. Calculate the maximum amount of money a thief could steal in one night without setting off the alarm.Copy the code- example
Input: [3,2,3, NULL,3, NULL,1] 3 / \ 2,3\3 1 Output: 7 Input: [3,4,5,1,3, NULL,1] 3 / \ 4 5 / \ 1 3 1 Output: 9 Explanation: The maximum amount a thief can steal in one night = 4 + 5 = 9.Copy the code- Answer key
For a node, it is possible to steal the left and right child nodes, or its own node and two grandchildren nodes without triggering the alarm. However, this node cannot directly obtain the value of the grandchild node, so the child node needs to return this information.
- Define each level of tasks and how to drive recursion
According to the returned values of the left and right child nodes, the maximum stealing scheme is selected. Recursion down the tree drives recursion.
- Is it clear what results the child node needs to return and what information the parent node needs to send in order to complete the tasks of this layer
You need to return the values of the left and right child and grandchild nodes. Since descendant nodes are also stolen and meet the principle of no alarm, the value of descendant nodes returned here is not only the value of descendant nodes themselves, but the value of stealing schemes containing child nodes or stealing schemes containing grandchildren nodes.
- Specify the termination conditions and the final question.
The recursion is terminated by returning 0 when a null node is encountered. So what they want to do is they want to do the optimal selection at the root of the tree.
- AC code
class Solution {
public:
int rob(TreeNode* root) {
auto ret = dfs(root);
return std::max(ret.first, ret.second);
}
// First is the maximum that contains root, second is the maximum that does not contain root
std::pair<int.int> dfs(TreeNode *root)
{
std::pair<int.int> ret = {0.0};
if(root == nullptr)
return ret;
auto left = dfs(root->left);
auto right = dfs(root->right);
If the root node is included, the left and right subtrees of root cannot be included
ret.first = left.second + right.second + root->val;
// Does not contain the value of the root node, then add up the maximum value of the subtree left and right root
ret.second = std::max(left.first, left.second) + std::max(right.first, right.second);
returnret; }};Copy the codeThe parent node only sends information (tasks) to its child nodes
Find the sum of numbers from the root node to the leaf node
Leetcode the original leetcode-cn.com/problems/su…
- Topic describes
You are given the root node of a binary tree. Each node in the tree contains a number between 0 and 9. Each path from root to leaf represents a number: for example, path 1 -> 2 -> 3 from root to leaf represents the number 123. Computes the sum of all numbers generated from the root node to the leaf node.Copy the code- example
Input: root = [4,9,0,5,1] output: 1026 The path from the root to the leaf node 4->9->5 represents the number 495. The path from the root to the leaf node 4->9->1 represents the number 491. The path from the root to the leaf node 4->0 represents the number 40Copy the code- Answer key
- Define each level of tasks and how to drive recursion
For each node, the calculation results passed from the root node to this layer are accumulated. And passed to the child nodes. Recursion down the tree drives recursion.
- Is it clear what results the child node needs to return and what information the parent node needs to send in order to complete the tasks of this layer
In this case, the direction is from the root to the leaf, and no child node is required to return the result. But the parent node is required to deliver its cumulative results.
- Specify the termination conditions and the final question.
Calculating the cumulative value of the leaf stops when it hits the leaf node. And finally they want to sum the values of all the leaves. The final result at the leaf needs to be returned, but it doesn’t need to be returned in a recursive function. It just needs to be stored in a global variable.
- AC code
class Solution {
public:
int sumNumbers(TreeNode* root) {
m_sum = 0;
dfs(root, 0);
return m_sum;
}
void dfs(TreeNode *tr, int father_val){
if(tr == nullptr) {return ;
}
int cur_val = 10 * father_val + tr->val;
if(tr->left == nullptr && tr->right == nullptr){
m_sum += cur_val;
}else{
dfs(tr->left, cur_val);
dfs(tr->right, cur_val); }}private:
int m_sum;
};
Copy the codeParent and child nodes need to pass information to each other (task)
The binary tree is reconstructed from the result of preorder and middle order traversal
Leetcode the original leetcode-cn.com/problems/zh…
- Topic describes
Enter the results of pre-order traversal and middle-order traversal of a binary tree, build the binary tree and return its root node. It is assumed that the result of both the preceding and the middle traversal of the input does not contain duplicate numbers.Copy the code- example
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null, 15,7]Copy the code- Answer key
There is no tree in bodhi, how to traverse the tree as before? There’s no tree, but you can still iterate recursively. To halve the result of a middle-order traversal is to traverse a binary tree.
According to the definition of pre-order traversal and middle-order traversal, the first node of pre-order traversal is in middle-order traversal, and the result of middle-order traversal can be divided into left and right sections. The left is the left subtree of the node, and the right is the right subtree of the node. It’s essentially a dichotomy of the right order traversal that’s called treification.
From the previous analysis, began to set.
- Define each level of tasks and how to drive recursion
Constructs the tree node of this layer and sets its left and right subtrees. Methods to drive recursion: Since there is no tree that can be recursed directly, the task of this layer also needs to divide the middle ordinal group into two segments according to the value of the preceding node, and the left and right segments are respectively used as the left and right subtrees for recursion.
- Determine what results the child node needs to return and what information the parent node needs to send in order to complete this layer’s tasks.
The child node returns the child root node of its construction, allowing the layer node to set the left and right subtrees. The parent node needs to deliver the pre-order and middle-order traversal number groups to be traversed.
- Specify the termination conditions and the final question
When the middle ordinal group is null, there is no data to construct the subtree, i.e. a null node. You can stop recursion at this point. And finally they want to return the first node of the construct.
- AC code
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return dfs(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
}
// The main reason to use templates is not to type long iterators. Perfect retweets are also a factor.
template<typename T>
TreeNode* dfs(T &&preStart, T preEnd, T inStart, T inEnd){
if(inStart == inEnd){
return nullptr;
}
auto pos = std::find(inStart, inEnd, *preStart);
TreeNode *tr = new TreeNode(*pos);
++preStart; // This has already been used.
tr->left = dfs(std::forward<T>(preStart), preEnd, inStart, pos);
tr->right = dfs(std::forward<T>(preStart), preEnd, std::next(pos), inEnd);
returntr; }};Copy the codeIf you are not familiar with C++11’s perfect forwarding, check out the following version
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
auto it = preorder.begin(a);Preoder.begin () will not be passed to DFS unless it is fixed to an lvalue
return dfs(it, preorder.end(), inorder.begin(), inorder.end());
}
template<typename T>
TreeNode* dfs(T &preStart, T preEnd, T inStart, T inEnd){
if(inStart == inEnd){
return nullptr;
}
auto pos = std::find(inStart, inEnd, *preStart);
TreeNode *tr = new TreeNode(*pos);
++preStart; // This has already been used.
tr->left = dfs(preStart, preEnd, inStart, pos);
tr->right = dfs(preStart, preEnd, std::next(pos), inEnd);
returntr; }};Copy the codeThe above code is O(N^2). If you want to optimize to O(N), you can first put the result and subscript of the middle order traversal into the hash map, and then change STD ::find to hash table lookup.
The largest binary tree
Leetcode the original leetcode-cn.com/problems/ma…
- Topic describes
Given an integer array nums with no repeating elements. A maximum binary tree built directly recursively from this array is defined as follows: The root of the binary tree is the largest element in the array NUMs. The left subtree is the maximum binary tree recursively constructed from the left of the maximum in the array. The right subtree is the largest binary tree recursively constructed from the right portion of the maximum value in the array. Returns the maximum binary tree built with the given array NUMs.Copy the code- example
Output: input: nums =,2,1,6,0,5 [3] [6,3,5, null, 2, 0, null, null, 1] : recursive calls as shown below: 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]. - An empty array with no child nodes. The maximum value in - [2,1] is 2, the left part is [], and the right part is [1]. - An empty array with no child nodes. - There is only one element, so the child node is a node with the value 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 the value 0. - An empty array with no child nodes.Copy the code- Answer key
This problem is similar to the previous problem of constructing a binary tree based on the results of preorder and middle order traversal
- AC code
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return dfs(nums.begin(), nums.end());
}
template<typename T>
TreeNode* dfs(T begin, T end)
{
if(begin == end)
return nullptr;
T it = std::max_element(begin, end);
TreeNode *tr = new TreeNode(*it);
tr->left = dfs(begin, it);
tr->right = dfs(std::next(it), end);
returntr; }};Copy the codeMaximum binary tree II
Leetcode the original leetcode-cn.com/problems/ma…
- Topic describes
Maximum tree definition: A tree in which the value of each node is greater than any other value in its children. Give the root node of the largest tree, root. As in the previous problem, the given tree is constructed recursively from list A (root = Construct(A)) using the Construct(A) routine: If A is empty, return NULL otherwise, let A[I] be the largest element of A. Create A root node with value A[I] root. The left subtree of root will be constructed as Construct([A[0], A[1]..., A[i-1]]). The right subtree of root will be constructed as Construct([A[I +1], A[I +2], A[a.length-1]]) return root notice that we are not given A directly, only A root = Construct(A). Suppose B is A copy of A and adds val at the end. The data in question guarantees that the values in B are different. Returns the Construct (B).Copy the code- example
Input: root = [4,1,3, null, null, 2], val = 5 output: [5, 4, null, 1, 3, null, null, 2] : A =,4,2,3 [1], B =,4,2,3,5 [1]Copy the code- Answer key
So they want to insert the value into the biggest tree, so that the tree is still the biggest tree. That is, find a good place to put the value that you want to insert.
- Define each level of tasks and how to drive recursion
If the value to be inserted is greater than that of the node at this layer, you need to create a new node to replace the node as the child node of the node. If the value to be inserted is smaller than the node in this layer, you can recurse to the left or right subtree.
- Determine what results the child node needs to return and what information the parent node needs to send in order to complete this layer’s tasks.
The child node returns the treated child root node, allowing the layer node to set the left and right subtrees directly. The processed subtree can be either the subtree after inserting the value to be inserted or the source subtree.
- Specify the termination conditions and the final question
When a leaf is traversed, it indicates that the value to be inserted is smaller than any value in the tree and can be used as a new leaf. If the insertion is done at the middle level, the termination recursion is returned. And when we do that, we’re done.
- AC code
class Solution {
public:
TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
if(root == nullptr)
return nullptr;
return dfs(root, val);
}
TreeNode* dfs(TreeNode *root, int val)
{
if(root == nullptr)
return new TreeNode(val);
if(root->val < val)
{
TreeNode *tr = new TreeNode(val);
tr->left = root;
return tr; // Return the new subtree after insertion
}
else
{
root->right = dfs(root->right, val);
return root; // return the source subtree}}};Copy the codeExpand the binary tree into a bidirectional linked list
Leetcode the original leetcode-cn.com/problems/er…
- Topic describes
Enter a binary search tree and convert the binary search tree into a sorted circular bidirectional list. You cannot create any new nodes. You can only adjust the Pointers to nodes in the tree.Copy the code- example
Input: root = [6],2,5,3,4 1, null, output: [1, null, 2, null, 3, null, 4, null, 5, null, 6] we want to convert the binary search tree to the bidirectional circular linked list. Each node in a linked list has a precursor and a successor pointer. For a bidirectional circular list, the first node is preceded by the last node, and the last node is succeeded by the first node. The figure below shows the linked list transformed from the binary search tree above. "Head" refers to the node with the smallest element in the list.Copy the code
In particular, we want to be able to do the conversion in place. When the transformation is complete, the left pointer of the node in the tree needs to point to the precursor, and the right pointer of the node in the tree needs to point to the successor. You also need to return a pointer to the first node in the list.Copy the code- Answer key a
The search binary tree is flattened into a linked list, and the order of the nodes in the list is the order of the middle order traversal. This causes the nodes of any subtree to be adjacent in the linked list. So all subtrees have to be flattened to make a linked list. For a subtree, when flattened, it is a continuous part of the final list. To join the list together, you need to provide the first and last nodes of the list. In recursion, the child node needs to return the head and tail of the flattened list to the parent node. So the parent can join the two lists together. The head node of the list is the leftmost node of the subtree, and the tail node is the rightmost node of the subtree. Therefore, the child node returns information to the parent node: the leftmost node and the rightmost node of the child node.
- Define each level of tasks and how to drive recursion
The way to drive the recursion is to directly recurse the left and right subtrees to get the left and right lists. The nodes of this layer are located in the middle of the two lists. You can join the left and right lists and nodes of this layer together.
- Is it clear what results the child node needs to return and what information the parent node needs to send in order to complete the tasks of this layer
Child nodes only need to return the first and last nodes of the list. The parent node does not need to deliver information.
- Specify the termination conditions and the final question.
Terminate when the subtree is empty. The root of the tree returns the top and bottom nodes that they’re asking for.
- AC code a
With the above analysis, it is easy to derive the following code.
class Solution {
public:
Node* treeToDoublyList(Node* root) {
if(root == nullptr)
return nullptr;
std::pair<Node*, Node*> p = dfs(root);
p.second->right = p.first;
p.first->left = p.second;
return p.first;
}
std::pair<Node*, Node*> dfs(Node *tr){
Node *leftest = nullptr;
Node *rightest = nullptr;
if(tr->left == nullptr){
leftest = tr;
}else{
// Recursive, let the subtree do its job.
std::pair<Node*, Node*> p = dfs(tr->left);
// Concatenate the list on the left with the TR node
leftest = p.first;
p.second->right = tr;
tr->left = p.second;
}
if(tr->right == nullptr){
rightest = tr;
}else{
// Recursive, let the subtree do its job
std::pair<Node*, Node*> p = dfs(tr->right);
// Concatenate the list with the tr node
rightest = p.second;
p.first->left = tr;
tr->right = p.first;
}
// Returns the result of this object
return std::make_pair(leftest, rightest); }};Copy the code- Answer key 2
Tired, don’t want to write. Here will brush at that time the notes made original copy. This note is also the main source of ideas for this article.
For a node tr, it should leave the left and right subtrees (recursively) to generate a sublist. For the first node in the list that the right subtree needs to return to, tr->right points to the returned node. The left subtree also returns the first node of the list, because the TR node needs that first node to cross off to its parent. In addition to requiring the left and right subtrees to return the first node of the list, they are also required to add specific nodes to the end of the list. For the left subtree, add tr; In the case of the right subtree, it is a node that the tr parent tells.
- AC code 2
class Solution {
public:
Node* treeToDoublyList(Node* root) {
if(root == nullptr)
return root;
// A temporary node is inserted at the end of the loop. Make treeToDoublyListCore
// The last node can be retrieved directly
Node *tmp = new Node;
Node *head = dfs(root, tmp);
Node *last = tmp->left;
last->right = head;
head->left = last;
return head;
}
Node* dfs(Node *tr, Node *rightNode)
{
if(tr->right == nullptr)
{
tr->right = rightNode;
rightNode->left = tr;
}
else
{
Node *first = dfs(tr->right, rightNode);
tr->right = first;
first->left = tr;
}
return tr->left == nullptr ? tr : dfs(tr->left, tr); }};Copy the codeThank you for your attention! More technical dry goods in the “wechat public number (code color)”.