Algorithm(8) Naive Tree

The typical algorithm questions based on the tree structure.

This article describes several key considerations of the tree and binary search tree, we first describe the commonly techniques and thinking perspectives to solve these type of problems and then we list several specific problem and there soluations, we may put these solutions into different blogs in future.

The list of sample questions is based on this table

This part mainly contains question which provides a tree structure explicitly. The more complexed question based on decision tree or search tree can be and different context is listed in another blog. In this blog, we only list the question that provide the tree structure as the input in explicit way. This table summarize the question listed in this article.

Traverse tree Modify tree structure Tree properties
(whole tree)
Tree properties
(search path
path sum, nodes)
Serilization Search with
map optimization
94,429,987 814,669,450
701,99,108
100,572,101
110,965,872
98
111,112,129
113,437,508
124,543,235
968,501,230
297 337

Key techniques and considerations

  • (1) Classification of the tree node, instead of classifying it into the leaf or null leaf, just assume it is null or not null, or more complex form such as 968 (covered or not covered, 450 is also a good classification example, leaf node, have 1 child, have two child), 257 classifies the node to null node, leaf node and not null node.

  • (2) From up to bottom, the lower level nodes need the information of the upper level nodes.

  • (3) From bottom to up, the left and right child tree returns root or specific value, the upper level nodes needs the information of the lower level nodes or subtrees. Make sure which is more eaiser. Sometimes knowing the child status then compute the parent status is more easier, some times knowing parent status then process child case is more easier. 337 is a good example in this case. 98 is a good example to try both bottom to up and up to the bottom case.

  • (4) Bst tree, the in order traverse (LNR) is the array with ascending values

  • (5) Typical strategy to insert or delete the node, how to acquire the parent pointer for different questions (the 450 can be a complex one for this type)

  • (6) The idea of calling level is important for these type of questions, For example, we may print the information of recursion level to debug the code. Besides, for the searching path, remember that the element need to be poped out after each level function call, this techniques are used in 257 and the 437.

  • (7) When there is the combination of tree and the string, the key step is to map the string into the tree structure logically and we ususlly does not need an explicit tree in that case. But we may use the recursion method. It is important to remember several typical questions and what are the gaps here.

Here are some key thinking perspectives, these ideas can also be used to solving other problems, these steps are useful especially when you do not have ideas for solving current problem

  • Consider the data structure adopted by the problem, from the domain specific problem to a cs algorithm problem, this step is comparatively simple for easy or medium question

  • Confirm the type of problem, typically type of problem is modify, search specific results or compute optimization situation. After confirming this, we can further move to another step.

  • For the problem of searching, we first need to figure out the total status and the total combinations, then we use the constrains and the techniques discussed above to narrow down these situations. For the problem of modifying, just be caring of common operations for create delete nodes, the tricks of keeping parent pointer etc.

  • Other specific type of problems (such as search possible solutions) are related to tree, but not totally related, we use another blog to discuss these questions (parathesis match, work search, sudoku problem, queens problem and puzzle problem).

Traverse tree

94. Binary Tree Inorder Traversal

This is really typical one, the inorder traversal represents the LNR traversal. The node type is divided into nullptr or not nullptr, this can be the basic framework for more complicated algorithm.

class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
help(root, ans);
return ans;
}

void help(TreeNode* root, vector<int>& ans){
if(root==nullptr){
return;
}

// left
help(root->left,ans);
// current
ans.push_back(root->val);
// right
help(root->right, ans);
}
};

144 and 145 are similar problems, they are preorder (NLR) and postorder (LRN) traversal, respectively. 589 and 590 is the N children problem.

429. N-ary Tree Level Order Traversal

how to process the height information? There is no associated variable defination in the tree structure. This is the code that use the BFS style code based on the queue. The key idea that label the level is to remember the queue size after each level. Then at the next iteration, we just need to pop out the node in the previous level, and then the remaning elements are nodes on the current level. We do similar things and move to the next iteration step by step.

// Time complexity O(n)
// Space complexity O(n)
class Solution {
public:
queue<Node*> q;
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> ans;
vector<int> temp;
help(root, ans, temp, true);
return ans;
}
void help(Node* root,vector<vector<int>>& ans,vector<int>& temp, bool iflast){
//put the temp into the ans if switch the height
//if the current node is null, hit a new level, then push
if(root==nullptr){
return;
}
q.push(root);
int levelsize = q.size();
while(q.empty()==false){
while(levelsize>0){
levelsize--;
Node* curr=q.front();
temp.push_back(curr->val);
q.pop();

for(int i=0;i<curr->children.size();i++){
q.push(curr->children[i]);
}
}
// this layer finish
ans.push_back(temp);
temp.clear();
// current queue size, there are qsize element
// the elements in the queue are elements at a new level now
levelsize = q.size();
}
return;
}
};

Another similar code is this one we basically need one while loop to adjust the q size and one for loop (or while loop) to monitor the number of current level.

The code can also be written in an recursive way. The general framework of recursion is easy to write, the key part is that we set the depth and insert the associated elements into the proper position. We also insert the empty array into the ans vector during the recursion process. The code of the recursive way is more clean. This is actually the dfs code, which is not the bfs code !!! The recursion call is in the dfs order.

class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> ans;
help(root, ans, 0);
return ans;
}

void helper(Node* root, vector<vector<int>>&ans, int depth){
if(root==nullptr){
return;
}
//if the new layer
if(ans.size()<(depth+1)){
ans.push_back({});
}
// visit node
ans[depth].push_back(root->val);
// call children recursively
for(auto child: root->children){
help(child, ans, depth+1);
}
}
};

Similar problem:

102 is also similar one, just using the level order, the code is simple when using the recursion method discussed above.

107 its input data structure is the binary tree, which is the simplified version of the 429. The 107 require the output sequence from the bottom to up. So we only need to add reverse(ans.begin(), ans.end()) before returning the ans.

104 is also similar one, just compute the maxdepth of the tree direactly.

987. Vertical Order Traversal of a Binary Tree

Using the data structure in a wise way is the key for this question. The first key of the map indicates the column, the second key indicates the row, the multiset indicates there are multiple elements in same column, row index and the elements is stored in ascending manner, and the elements can also be repeated in the set.

class Solution {
public:
vector<vector<int>> verticalTraversal(TreeNode* root) {
// why use the multiset: check this data [3,1,4,0,2,2]
map<int, map<int, multiset<int>>> mymap;
helper(root, mymap, 0, 0);
vector<vector<int>> ans (mymap.size());
int i=0;
for(auto it:mymap){
for(auto itmapset : it.second){
for(auto itset: itmapset.second){
//printf("itset %d\n",itset);
ans[i].push_back(itset);
}
}
i++;
}
return ans;
}

void helper(TreeNode* root, map<int, map<int, multiset<int>>>& mymap, int row, int column){
if(root==nullptr){
return;
}
mymap[column][row].insert(root->val);
//children
//left
helper(root->left, mymap, row+1, column-1);
//right
helper(root->right, mymap, row+1, column+1);
return;
}
};

Compared with using a grid, using the ordered map is more simple, other soluation also use the pair as the key of the map

Similar questions:

1302, just sum up the deepest leaves, the question is, how do we know it is the deepest leaves. The idea is just using a spearate depth variable and keep the newest value, then add varaible into the sum

// one solution for 1302
class Solution {
public:
int maxDepth=0;
int layersum = 0;
int deepestLeavesSum(TreeNode* root) {
helper(root, 0);
return layersum;
}
void helper(TreeNode* root, int currDepth){
if(root==nullptr){
return;
}
//visit node, add some trim operation
if(root->left==nullptr && root->right==nullptr){
if(currDepth>maxDepth){
maxDepth = currDepth;
layersum = 0;
}
if(currDepth == maxDepth){
layersum = layersum + root->val;
}
}
//move to the children
helper(root->left,currDepth+1);
helper(root->right,currDepth+1);
}
};

257 Binary Tree Paths

This question requires to print out the searching paths, one key idea is to adjust current searching path. We use a vector store the searching path, when current level of recursion finish, we then pop back the last element in the vector, by this way, we can always make sure the element in the vector is located in the current path. The similar ideas is also used in the 437, in that case, we decrease the associated path number after leaving the current recursion call each time. The search path here is based on the idea of the dfs essentially.

class Solution {
vector<string> m_ans;
vector<int> m_path;
public:
vector<string> binaryTreePaths(TreeNode* root) {
helper(root);
return m_ans;
}

void helper(TreeNode* root){
if(root==nullptr){
return;
}
//visit leaf node
m_path.push_back(root->val);

//if leaf, add path info
if(root->left == nullptr && root->right == nullptr){
//put currpath into the m_ans
string tempstr;
for(int i=0;i<m_path.size();i++){
if(i==0){
tempstr=tempstr+to_string(m_path[i]);
}else{
tempstr=tempstr+"->"+to_string(m_path[i]);
}
}
m_ans.push_back(tempstr);

//remove one elem
//the leaf node return earlyer at this case
m_path.pop_back();
return;
}

//children
helper(root->left);
helper(root->right);

//remove elem in current level
m_path.pop_back();
}
};

Tree properties (whole tree)

Compare if two trees are same, mirror or satisfies certain constraints

100 check the same tree, we can use any type of iteration method discussed above, if there is null equal during the recursive process, return the false, otherwise, return true.

// be carefule for the several special cases for deciding the same tree
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p==nullptr && q){
return false;
}
if(p && q==nullptr){
return false;
}
if(p && q){
//visit
if(p->val != q->val){
return false;
}

//check the child
bool leftSame = isSameTree(p->left, q->left);

if(leftSame==false){
return false;
}

bool rightSame = isSameTree(p->right, q->right);

if(rightSame==false){
return false;
}
}
return true;
}
};

572 Subtree of Another Tree, this is the updated version for comparing if two trees are same with each other. Traverse the original tree based on NLR sequence, if the node value equals with the subroot value, executed comparision operation. Otherwise, continue check.

//572. Subtree of Another Tree
class Solution {
public:
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
//edge cases
if(!root && !subRoot){
return true;
}
if(!subRoot){
// subroot is null but root is not
return true;
}
if(!root){
// the root is null but subRoot is not null
return false;
}

//go through left and right
bool leftContain = isSubtree(root->left, subRoot);
bool rightContain = isSubtree(root->right, subRoot);

if(leftContain || rightContain){
return true;
}

if(leftContain == false && rightContain==false){
if(root->val == subRoot->val){
bool same=isSameTree(root, subRoot);
if(same){
return true;
}
}
}

return false;
}

bool isSameTree(TreeNode* p, TreeNode* q) {
if(p==nullptr && q){
return false;
}
if(p && q==nullptr){
return false;
}
if(p && q){
//visit
if(p->val != q->val){
return false;
}

//check the child
bool leftSame = isSameTree(p->left, q->left);

if(leftSame==false){
return false;
}

bool rightSame = isSameTree(p->right, q->right);

if(rightSame==false){
return false;
}
}
return true;
}
};

The above code reuse the function of 100, it still looks a little bit complicated and error prone. For the edge cases, we need to consider four situations and confirm the case that one of the child is nullptr. It also uses the idea of compare left part then compare the right part, since there is a return value of the function. For example, after deciding that the left part do not contain subtree, the right part does not contain subtree and the current root does not contains subtree, we can returns the false.

The 101 symmetric tree is also a similar question, the condition of mirror is just reverse the left and right, one case is right to left, another case is right to left, to decide if they are equal. This is similar with previous one, the difference is the traversal sequence. The origianl thought is to use LNR to traverse left and use RNL to traverse right, then compare the results. But this input [1,2,2,2,null,2] have the same results eigher for LNR and RNL. So it is not uniquely to decide if two parts are mirror of each other. Although the result is straightforward, it is not easy to provide the reuslts at the first glance.

class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(root==nullptr){
return true;
}
return Compare(root->left, root->right);
}

bool Compare(TreeNode* p, TreeNode* q){
if(p==nullptr && q){
return false;
}
if(p && q == nullptr){
return false;
}
if(p && q){
//visit
if(p->val != q->val){
return false;
}
bool leftSame = Compare(p->left, q->right);
if(leftSame==false){
return false;
}
bool rightSame = Compare(p->right, q->left);
if(rightSame==false){
return false;
}
}
return true;
}
};

110 check if the tree is balanced. This is a little bit special, since it introduce the idea from the bottom to up. Namely, the helper function returns some information and this information will be used by the upper level. These type of paradigm is used a lot when modify the tree structure.

class Solution {
public:
bool isBalanced(TreeNode* root) {
int height=0;
return helper(root, height);
}

bool helper(TreeNode* root, int& height){
if(!root){
return true;
}
//left balanced
int leftHeight=0;
bool leftBalanced = helper(root->left, leftHeight);

//right balanced
int rightHeight=0;
bool rightBalanced = helper(root->right, rightHeight);
height=max(leftHeight,rightHeight)+1;

//check diff
if(leftBalanced && rightBalanced){
if(abs(leftHeight-rightHeight)<=1){
return true;
}
}
return false;
}
};

965 is also a similar one, just simple checking based on the bottom to up recursion. The properties for these questions is to detect the results of the subtree first and then use the return results to decide the current results.

872 is a similar one with the simple background, the idea of code classification is good. null ptr, leaf, one child, two childern. Pay attention to the sequence of the checking and make sure all situations are considered.

class Solution {
public:
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
//get leaf sequecnce of the first one
vector<int> seq1;
getLeafSeq(root1, seq1);
// get leaf sequence of the second one
vector<int> seq2;
getLeafSeq(root2, seq2);

if(seq1.size()!=seq2.size()){
return false;
}
for(int i=0;i<seq1.size();i++){
if(seq1[i]!=seq2[i]){
return false;
}
}
return true;
}

void getLeafSeq(TreeNode* root, vector<int>& ans){
//null
if(root==nullptr){
return;
}
//leaf
if(root->left==nullptr && root->right==nullptr){
ans.push_back(root->val);
return;
}
//one child
if(root->left){
getLeafSeq(root->left, ans);
}
if(root->right){
getLeafSeq(root->right, ans);
}
return;
}
};

98. Validate Binary Search Tree

The idea is not complicated, we make sure the left subtree is valid, the right subtree is valid, then adding the root into the tree to make the current tree is valid. There are two points, one is that we need to record the max value of the left tree to make sure current node is larger than all value in the left tree. Similar for the right subtree. Another is that the data range of the node is -2^31-1 to 2^31
This may lead to the case that the left or right node equals to the INT_MAX or INT_MIN (which is the initial status and the status when there is null node). Therefore, we need to consider the case when there is one child and two children separately to make some edge cases work. Otherwise, when the node contains INT_MAX or INT_MIN, the comparision might fail, since we could not provide a boundry value that contains these two values for integrer.

class Solution {
public:
int maxinit = INT_MAX;
int mininit = INT_MIN;

bool isValidBST(TreeNode* root) {
return helper(root, maxinit, mininit);
}

bool helper(TreeNode* root, int& minV, int&maxV){
//null node
if(root==nullptr){
return true;
}

//leaf node
if(root->left==nullptr && root->right==nullptr){
maxV = root->val;
minV = root->val;
return true;
}

//one child node
int lMinV= minV;
int lMaxV= maxV;
bool lbst = helper(root->left, lMinV, lMaxV);

// keep update the max value of the left child tree
//printf("l minV %d maxV %d ",lMinV, lMaxV);
if(root->left!=nullptr){
if(lbst && lMaxV>=root->val){
return false;
}
if(lbst==false) return false;
}

int rMinV= minV;
int rMaxV= maxV;
// keep the min value of the right child tree
// the minV here is influenced
bool rbst = helper(root->right, rMinV, rMaxV);
if(root->right!=nullptr){
if(rbst&&rMinV<=root->val){
return false;
}
if(rbst==false) return false;
}
// two children case
maxV = max(maxV,max(rMaxV, root->val));
minV = min(minV,min(lMinV, root->val));
return true;
}
};

We can also set the boundry value at the long long int to simplify the code, but we need to transfer the root value into the long long type when doing the comparison:

class Solution {
public:
long long int maxinit = LLONG_MAX;
long long int mininit = LLONG_MIN;

bool isValidBST(TreeNode* root) {

return help(root, maxinit, mininit);
}

bool help(TreeNode* root, long long int& minV, long long int&maxV){

if(root==nullptr){
return true;
}

if(root->left==nullptr && root->right==nullptr){
maxV = root->val;
minV = root->val;
return true;
}

long long int lMinV= minV;
long long int lMaxV= maxV;
// all nullptr, return true
bool lbst = help(root->left, lMinV, lMaxV);
if(!lbst) return false;

long long int rMinV= minV;
long long int rMaxV= maxV;
// keep the min value of the right child tree
// the minV here is influenced
bool rbst = help(root->right, rMinV, rMaxV);
if(!rbst) return false;

//current
if(root->val<=lMaxV || root->val>=rMinV){
return false;
}

maxV = max(rMaxV, (long long int)root->val);
minV = min(lMinV, (long long int)root->val);
return true;
}
};

Another idea is from the top to down, actually the code is more simpler in this case, we start from the root node and then narrow down the range of the child gradually, we set the vmin and vmax as the long int to make sure the results also correct when node equals to the INT_MIN or INT_MAX.

class Solution {
public:

bool isValidBST(TreeNode* root) {

return helper(root, LLONG_MIN, LLONG_MAX);
}

bool helper(TreeNode* root, long int vmin, long int vmax){

if(!root) return true;

if(root->val <= vmin || root->val>= vmax){
return false;
}

bool lvalid = helper(root->left, vmin, root->val);
if(lvalid==false) return false;

bool rvalid = helper(root->right, root->val, vmax);
if(rvalid==false) return false;

return true;
}
};

Tree properties (path, path sum, nodes)

111 check the minimum depth. It also use the similar strategy. Check the min depth of the left and right part, and then return the min of the left and right value plus one. Be careful for processing the null node. Since we just return 0 direactly. When we compare the return value, this node is not accounted into the depth of the tree. For the test case such as [2,null,3,null,4,null,5,null,6], the return value is 5. When we check the min value, we do not consider the return value with the 0. Since the leaf node is the node with no children. Which should return 1 at least.

// 111 Minimum Depth of Binary Tree
class Solution {
int mindepth = 0;
public:
int minDepth(TreeNode* root) {
return helper(root);
}
int helper(TreeNode* root){
if(root==nullptr){
return 0;
}
//ldepth
int ldepth = helper(root->left);
//rdpeth
int rdepth=helper(root->right);
//current depth
int currdepth = 0;
if(ldepth==0 && rdepth !=0){
currdepth = rdepth+1;
}else if (rdepth==0 && ldepth!=0){
currdepth = ldepth+1;
}else{
currdepth = min (ldepth, rdepth)+1;
}
return currdepth;
}
};

112.Path Sum, using the NLR to traverse the tree and decrease the target sum each time going to the next level. Only return true at the case where node is the leaf node and satisfies the targeted. Using the idea from the up to bottom is more natural for this one. The idea of considering things in sequence and in a complete way is important, the null node, the leaf node and the non-leaf node.

Actually, the good practice here is to consider the edge case firstly, since we can return it direactly and to not do the subsequent checking, then the remaning logic is the general case. So, the good practice for the recursion operation is to write the return entry firstly and then check the recursion part, but when we thinking it, we may consider the recursion part firstly and then the return part.

class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if(root == nullptr){
return false;
}

//visit current node
//if leaf
if(root->left == nullptr && root->right == nullptr){
if(targetSum==root->val){
return true;
}
}

//check left and right
bool left = hasPathSum(root->left, targetSum-root->val);
if(left){
return true;
}
bool right = hasPathSum(root->right, targetSum-root->val);
if(right){
return true;
}
return false;
}

};

129 Sum Root to Leaf Numbers is a similar question of 112, just times 10 when visiting the leaf node when adding the new path.

113 is the updated version of the 112, it requires to memory the specific path that satisfies the requirments, it is a typical search problem (both the start and the end of the search path is clear). This idea and associated code can be the framework for many more complicated problem.

//113 Path Sum II
class Solution {
vector<vector<int>> m_ans;
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
helper(root, targetSum, {});
return m_ans;
}

void helper(TreeNode* root, int targetSum, vector<int> currpath){
//null node
if(root==nullptr){
return;
}

//leaf node
if(root->left == nullptr && root->right == nullptr){
currpath.push_back(root->val);
//put temp to ans if satisfies requrements
if(root->val == targetSum){
m_ans.push_back(currpath);
}
}

//non-leaf node
//update current path
//search sub tree
currpath.push_back(root->val);
helper(root->left, targetSum-root->val, currpath);
helper(root->right, targetSum-root->val, currpath);
return;
}
};

437(tricky) This is the updated version of the path sum. Compared with the previous one, the started position is not clear, the end of the path is also not clear.

special cases

[1,null,2,null,3,null,4,null,5]
3
[1,-2,-3,1,3,-2,null,-1]
1

solution1, use naive recursion, there might be time limit exceeded issue (did not realize the issue of the start and end point)

//version 1, error prone
//it requires to express the start point or end point clearly
class Solution {
int m_pathNum=0;
int m_origianlTarget=0;
public:
int pathSum(TreeNode* root, int targetSum) {
m_origianlTarget = targetSum;
helper(root, {}, targetSum, true, 0);
return m_pathNum;
}
//runtime issue for this code
void helper(TreeNode* root, vector<int> path, int temptargetSum, bool parentAdded, int level){
//null
if(root==nullptr){
return;
}

//path does not contains root, use the origianl target
//this should be considered firstly
//this can be called multiple times potentially
//first node, call this, otherwise, use the tempsum
if(parentAdded==false || path.size()==0){
//potentially start point
helper(root->left, {}, m_origianlTarget, false, level+1);
helper(root->right, {},m_origianlTarget, false, level+1);
}


//path contains the current node
//visit current
//bool isend = false;
if(root->val == temptargetSum){
if(parentAdded==true || path.size()==0){
//potentially end point
m_pathNum++;
}
}

//path contains root
path.push_back(root->val);
helper(root->left, path,temptargetSum-root->val, true, level+1);
helper(root->right, path,temptargetSum-root->val, true, level+1);
}
};

The following code is the optimization of the version 1, the key point is to figure out if the current node is at the start position or at the following position, that is really important, use equals to 0 to decide the condition is more simplifier than the origianl case,we need to type fewer words in this case.

class Solution {
int m_pathNum=0;
long long m_origianlTarget=0;
public:
int pathSum(TreeNode* root, long long targetSum) {
m_origianlTarget = targetSum;
helper(root, targetSum, true);
return m_pathNum;
}
//runtime issue for this code
void helper(TreeNode* root,long long int temptargetSum, bool ifstart){
//null
if(root==nullptr){
return;
}

//first node, call this, otherwise, use the tempsum
if(ifstart){
//start point
helper(root->left, m_origianlTarget, true);
helper(root->right, m_origianlTarget, true);
}

temptargetSum-=root->val;
if(temptargetSum == 0){
//for the end node, do not check the subsequent nodes
m_pathNum++;
}

//path contains root, other nodes are followers
//still check till the last one, the node can be negative
//there value may conteract with each other
helper(root->left, temptargetSum, false);
helper(root->right, temptargetSum, false);
}
};

This code is much more simple and refer to this blog , attention that for the first layer, the function name is the pathSum instead of the helper.

class Solution {
public:
int pathSum(TreeNode* root, long long int targetSum) {
if(!root) return 0;
return helper(root, targetSum)+pathSum(root->left, targetSum)+pathSum(root->right, targetSum);
}

int helper(TreeNode* root, long long int tempsum){
if(root==nullptr){
return 0;
}

tempsum -= root->val;
return (tempsum == 0 ? 1 : 0)+helper(root->left,tempsum)+helper(root->right,tempsum);

}
};

Lesson: one important idea is how to debug in recursion code: we might add the level into the print info, this can be an indicator and it can change the flattern code into the hierachy code and check the horizental and vertical. By doing this, we can find an error in our origianl code, at that time, we forget to add the condition when the path is just started. However, it is difficult to figure it out and understanding the code behaviours without the help of the debug info.

This code can be further optimized based on the 560 that computes the prefix sum. The single path in 560 changes to the multiple path on the tree for this question. Here is the optimization version for this question based on the idea of 560

class Solution {
int m_pathNum=0;
int m_count = 0;
unordered_map< long int, int> psum;
public:
int pathSum(TreeNode* root, long targetSum) {
//for the case when the element itsself equals to the targetSum
psum[0]=1;
helper(root, targetSum, 0);
return m_count;
}

void helper(TreeNode* root, long int targetSum, long currentSum){
//null
if(root==nullptr){
return;
}

//visit current node
//visit left and right from up to bottom
currentSum = currentSum+root->val;

int previousSum = currentSum - targetSum;
//printf("previousSum %d ", previousSum);
m_count = m_count+psum[previousSum];

//put current sum into the map
//default value is 0 for empty element
psum[currentSum]++;

helper(root->left, targetSum, currentSum);
helper(root->right, targetSum, currentSum);

//this is a really important part from the single path sum to the tree based path sum
//this is much smarter than copy the map between each recursion call
psum[currentSum]--;
}
};

The main part of visiting the node is same with the 560, main difference is that, remember to decrease specific elements from map after each call. Essentially, we need a different map for each path, but copy past map direactlly in each call is also time consuming, so we just adjust values in the map dynamically to make sure it works for different path.

508. Most Frequent Subtree Sum

The traversal part is common one, using the idea from the bottom to up, the subtree returns a particular value. The extra part is to use a map to keep track of the sum during the tree traversal process. When the max freq is updated, we clear the ans, when freq of current sum equals to the max freq, we push the current sum, when the current sum is less than freq, we do nothing. (when there is tie means there are same frequent number for the two cases)

Start and the end of the path sum is comparatively clear in this question, which decrease its level of difficulty.

class Solution {
int maxFreq = 0;
//key is sum value is freq
unordered_map<int, int> freMap;
public:
vector<int> findFrequentTreeSum(TreeNode* root) {
vector<int> ans;
helper(root, ans);
return ans;
}

int helper(TreeNode* root, vector<int>& ans){

if(!root) return 0;

//get left sum
int leftSum = helper(root->left, ans);

//get right sum
int rightSum = helper(root->right, ans);

//with the current sum
int currSum = leftSum+rightSum+root->val;

//compute freq, if not exist, default is 0
int currFreq = freMap[currSum]+1;
freMap[currSum]=currFreq;

if(maxFreq<currFreq){
//update the MaxFreq and ans
ans.clear();
maxFreq = currFreq;
// when equal, current freq is the maximum one update ans
ans.push_back(currSum);
}else if(maxFreq==currFreq){
ans.push_back(currSum);
}else{
//do nothing when large than current
}

return currSum;
}
};

124 Binary Tree Maximum Path Sum

The setting of the question is not that much straightforward and the start and end point of the path is not certained. We could confirm the general framework of the question, and use the bottom to up method approach. The tricky part is to make sure the return value and how to visit the current node.

The key thinking perspective is considering if the current node is included in the path. The maximum path can be following several options: left sum path + root, right sum path + root, left sum path + root + right sum path, or just the root itself (this situation is easy to be forgottern), since the node value can be negative, all these situations can be the maximum case.

The return part is also tricky, we just return the max value among the left side, the right side and the node itsself. Instead of returing the current possible max path sum. Since we just needs the left path or right path of the subtree to construct the new path. Anyway, the code is straightforward and the answer might need some time to come up with. Since the minpath and the return value for each recurssion call are two different variables here.

class Solution {
int maxSum = INT_MIN;
public:
int maxPathSum(TreeNode* root) {
helper(root);
return maxSum;
}

int helper(TreeNode* root){
if(root==nullptr) return 0;
//left
int lpsum = helper(root->left);
//right
int rpsum = helper(root->right);

//visit & compare
int lrsum = lpsum+root->val;
maxSum = max(maxSum, lrsum);
int rrsum = rpsum+root->val;
maxSum = max(maxSum, rrsum);
int lrrsum = lpsum+root->val+rpsum;
maxSum = max(maxSum, lrrsum);

//single node without the child
//may also be the largest one
maxSum = max(maxSum, root->val);
return max(max(lrsum, rrsum),root->val);
}
};

543. Diameter of Binary Tree

One similar question is the 543 which compute the diameter of the tree, these two questions use similar strategy and code framework. The 543 can be the foundataion of this question. The important point is that the helper function should not return the whole length, and it should return the max of left path or right path of the subtree. Another smart point is that they return -1 in their code when there is nullptr, which simplifies the expression from 2 layer node classification to 1 layer node classification.

class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
int maxpath=0;
childp(root,maxpath);
return maxpath;
}

int childp(TreeNode* root, int& maxpath){
if(root==nullptr){
return -1;
}
// when connect with the root, the path length should increase 1
int lpath = childp(root->left,maxpath)+1;
int rpath = childp(root->right,maxpath)+1;
maxpath = max(maxpath, lpath+rpath);
return max(lpath,rpath);
}
};

687. Longest Univalue Path

The idea of this question is not diffecult, it is a little bit similar with previous several questions, the key part is consider every situation clearly

For the version1, we calssify the node by null, leave node, one child, two children case. Then in the two children case, we further consider the relationship between the root node and the child node.

class Solution {
int maxpath;
public:
int longestUnivaluePath(TreeNode* root) {
lup(root);
return maxpath;
}

int lup(TreeNode* root){
//root null
if(root==nullptr){
return 0;
}

//leaf node
if(root->left==nullptr && root->right==nullptr){
return 0;
}

//at least one child
int lpath = lup(root->left);
int rpath = lup(root->right);

//one child case
if(root->left && root->right==nullptr){
if(root->val == root->left->val){
lpath++;
}else{
lpath=0;
}
maxpath=max(maxpath,lpath);
return lpath;
}

if(root->right && root->left==nullptr){
if(root->val == root->right->val){
rpath++;
}else{
rpath=0;
}
maxpath=max(maxpath,rpath);
return rpath;
}

//two children case
//both left and right exist

//if root node not equals to both side
if(root->val != root->left->val && root->val != root->right->val){
maxpath=max(maxpath,0);
return 0;
}

//root node equals to both side
if(root->val == root->left->val&&root->val == root->right->val){
maxpath=max(maxpath,lpath+1+rpath+1);
return max(lpath+1, rpath+1);
}

//if root node eqauls to one side
//left side
if(root->val == root->left->val){
maxpath=max(maxpath,lpath+1);
return lpath+1;
}

//rside
maxpath=max(maxpath,rpath+1);
return rpath+1;
}

For the case2, we kind of merge the situation where there is one children and two
children case. Since when wen want to decide the situation of two children, we need to first decide the case when there is one children.

class Solution {
int maxpath;
public:
int longestUnivaluePath(TreeNode* root) {
lup(root);
return maxpath;
}

int lup(TreeNode* root){
if(root==nullptr){
return 0;
}

int lpath = lup(root->left);
int rpath = lup(root->right);

if(root->left){
if(root->val == root->left->val){
lpath++;
}else{
lpath=0;
}
maxpath=max(maxpath,lpath);
}

if(root->right){
if(root->val == root->right->val){
rpath++;
}else{
rpath=0;
}
maxpath=max(maxpath,rpath);
//consider the case that root equals to child
if(root->left&&root->val == root->left->val&&root->val == root->right->val){
maxpath=max(maxpath,lpath+rpath);
}
}
return max(lpath,rpath);
}
};

236(235). Lowest Common Ancestor of a Binary Tree

The naive solution is to use the idea based on the 257 which can remember the path of the tree traverse based on the dfs. When the node comes to the p, remember the path. When the node comdes to the q, remember the path. Then compare two path to find the last one that is same with each other. This node is the LCA node. For this solution, remember that we can not guarantee the sequence to find the p or q, it is possible to find p first or find the q first.

class Solution {
vector<TreeNode*> m_pathp;
vector<TreeNode*> m_pathq;
vector<TreeNode*> m_currpath;

public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
bool findp = false;
bool findq = false;

helper(root, p, q, findp, findq);
//fill int the m_pathp and m_pathq
int index = min(m_pathp.size(), m_pathq.size());
TreeNode* temp = nullptr;
//the unique value must exist
for(int i=0;i<index;i++){
printf(" %d ", m_pathp[i]->val);
if(m_pathp[i]->val!=m_pathq[i]->val){
//find the first different node on the path
break;
}
temp=m_pathp[i];
}
return temp;
}

//the first one can be either p or q
void helper(TreeNode* root, TreeNode* p, TreeNode* q, bool& findp, bool& findq){
if(root==nullptr){
return;
}

if(findp == true && findq == true){
return;
}

//visit node in path
m_currpath.push_back(root);

//when node comes to p
if(root->val==p->val){
//find p
//snapshot path
m_pathp = m_currpath;
findp = true;
}

//when node comes to q
//compare with previous path
if(root->val==q->val){
//find q
//find the correct path
m_pathq = m_currpath;
findq = true;
}

//left and right
helper(root->left, p, q, findp, findq);
helper(root->right, p, q, findp, findq);
//remove last element
m_currpath.pop_back();
}
};

This is another solution for this question. It use the idea that combines both top to down and bottom to up, it uses both current value and the value of lchild or rchild to decide the least common node in the tree. This method can avoid some unnecessary recursion operations.

It can decrease some search path depending the position of p and q. Consider the three node, current node (c), p and q. There are several possibilities about their positions:

a)p and q are not at the subtree of the c, return null in this case.
b)p and q are at the left subtree and right subtree respectively, return c in this case.
c)p and q are at one subtree of the c.

There are two further situations for the case c), the first one is that the c equals to p or q, return the c direactly in this case. Another situation is that the c not equals to p or q, in this case, return the lchild or rchild that is not null.

Here is a good explanation for this question (https://www.youtube.com/watch?v=KobQcxdaZKY)

class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//check current node
if(root == nullptr){
//for processing the edge case
return nullptr;
}

//current is p or q, return direactly
if(root->val == p->val || root->val == q->val){
return root;
}

//lchild
TreeNode* lchild = lowestCommonAncestor(root->left, p, q);
//rchild
TreeNode* rchild = lowestCommonAncestor(root->right, p, q);

//if both of them is null
if(lchild == nullptr && rchild ==nullptr){
// not contain p q in subtree
return nullptr;
}

//if both of them is not null
if(lchild && rchild){
//current is the lsc
return root;
}

//if one of them is null, return the specific one
//use conditional operator if we must return sth
return lchild==nullptr?rchild:lchild;
}
};

968. Binary Tree Cameras

It looks like a dp problem, since for each step, we can choose place camera or not

There is one answer looks a little bit complicated, but we considered things in a systamaticall way. Nameyly, null node, one child case and two children case. The status transfer between the two levels of the tree is important for solving the problem.

One tricky part is that when both left and right is the no camera but covered status, we have two options for the current node, either put camera here or weight for its parent. It looks that the dp approach is more general soluation. By analyzing this problem we can find that iftop is true, we prefer to put camera, other wise, we wait for the upper level node to put the camera.

I still did not figure out the how to compress the one child case, some code returns the camera monitored status when the node is null.

// from top to down not right, for the case that medium node is monitored, we added more node
class Solution {

public:

enum STATUS {CM = 0, NCM = 1, NCNM=2};
int ans=0;
int minCameraCover(TreeNode* root) {
//root is null
if(root==nullptr){
return 0;
}

//only one layer
if(root->left == nullptr && root->right==nullptr){
return 1;
}

//at least two layers
helper(root, true);
return ans;
}

//when it is not at the top position, we can always postpone the choice
STATUS helper(TreeNode* root, bool iftop){
//leaf node
if(root->left == nullptr && root->right ==nullptr){
return STATUS::NCNM;
}

// check left status
STATUS lstatus;
STATUS rstatus;

if(root->left){
lstatus = helper(root->left, false);
}

if(root->right){
rstatus = helper(root->right,false);
}


// left child
if(root->left == nullptr){
//check the right part
if(rstatus == STATUS::NCNM){
ans++;
return STATUS::CM;
}else if(rstatus == STATUS::NCM){
if(iftop){
ans++;
return STATUS::CM;
}else{
return STATUS::NCNM;
}
}
else{
return STATUS::NCM;
}
}

if(root->right == nullptr){
//check lstatus
if(lstatus == STATUS::NCNM){
ans++;
return STATUS::CM;
}else if(lstatus == STATUS::NCM){
if(iftop){
ans++;
return STATUS::CM;
}else{
return STATUS::NCNM;
}
}else{
return STATUS::NCM;
}
}


// two children
if(lstatus == STATUS::NCM && rstatus == STATUS::NCM){
//there are two options when both children are ncamera covered
if(iftop){
ans++;
return STATUS::CM;
}else{
return STATUS::NCNM;
}
}

if(lstatus == STATUS::NCNM || rstatus == STATUS::NCNM){
ans++;
return STATUS::CM;
}

//other cases
return STATUS::NCM;
}
};

After simplifying the code and assume the null node is the dummy node with the status NCM, we can get this simple code, although the code is simple, but the logical process to create this code is not simple, we need to consider all 3*3 possibilities and compress them into the simplified form as follows:

class Solution {   
public:
enum STATUS {CM = 0, NCM = 1, NCNM=2};
int ans=0;
int minCameraCover(TreeNode* root) {
//root is null
if(root==nullptr){
return 0;
}
//at least two layers
helper(root, true);
return ans;
}

//when it is not at the top position, we can always postpone the choice
STATUS helper(TreeNode* root, bool iftop){
//null
if(root == nullptr){
return STATUS::NCM;
}

STATUS lstatus = helper(root->left, false);
STATUS rstatus = helper(root->right, false);

// two children, the null node can be viewed as a dummy child
if(lstatus == STATUS::NCM && rstatus == STATUS::NCM){
//there are two options when both children are ncamera covered
if(iftop){
ans++;
return STATUS::CM;
}else{
return STATUS::NCNM;
}
}

if(lstatus == STATUS::NCNM || rstatus == STATUS::NCNM){
ans++;
return STATUS::CM;
}

//other cases
return STATUS::NCM;
}
};

979. Distribute Coins in Binary Tree

The code is easy, but the thinking perspective is important and it is not easy to get that point. We use the bottom to up method during the search, the return value for each layer represents how many coins is needed to make the current node and its subtree to satisfy the constraints (this idea is the key for solving the problem). For the simple case, such as the leaf node, the return value of the subtree is 0, they do not need extra coin move. For the case [3,0,0], at the node with value of 3, the return value of the left and right subtree is -1, we need move 1 conin to them. Then in order to make the node with value 3 become case that satisfies the requirements, we need to move 3-1 = 2. Adding this value with two return results, they become 2-1-1=0, so we do not need extra move. When we compute the move count, we use the abs value, no matter we move from current node or move to the current node, the move count through the edge should add one.

class Solution {
public:
int moveNum=0;
int distributeCoins(TreeNode* root) {
help(root);
return moveNum;
}
int help(TreeNode* root){
if(root==nullptr){
return 0;
}
//need how many coins
//the l and r can be balanced
int lcc=help(root->left);
int rcc=help(root->right);
//if the nullptr is not 1, we need to consider more cases here
//move one coin each time
moveNum = moveNum+abs(lcc)+abs(rcc);
int currentNeed = lcc+rcc+(root->val-1);
return currentNeed;
}
};

530 and 700 are similar questions that use the bst tree. 501 is also a similar one, the idea of updating the most frequent elements and associated length is inspiring. We consider three exclusive cases when checking the current node.

One tricky case is sth like [1,null, 2,2] do not update the recorded value based on the principle such as if current elem eqauls to the previous one. Since we do not know if there are more subsequent elements. For each step, we assume it is the last element.

When there is [1,null, 2] the ans vector contains 1 and 2, then move to the next, update the count, then clear the ans, then push 2 again. The key point here is we actually push the element 2 into the vector twice.

501. Find Mode in Binary Search Tree

class Solution {
public:
int recordLongest=0;
// the continuous value before visiting current node
int tempk=0;
int tempprev=INT_MIN;
vector<int> findMode(TreeNode* root) {
//go through LNR
vector<int> ans;
//init values
help(root,ans);
return ans;
}

void help(TreeNode* root, vector<int>& ans){
if(root==nullptr){
return;
}

// go through left
help(root->left, ans);

if(root->val!=tempprev){
tempk=1;
}else{
tempk++;
}

if(tempk>recordLongest){
ans.clear();
//printf("tempk %d push %d ", tempk, root->val);
ans.push_back(root->val);
recordLongest=tempk;
}else if(tempk==recordLongest){
ans.push_back(root->val);
}else{
//do nothing when the tempk<recordLongest
}
tempprev = root->val;
// go through right
help(root->right, ans);
}
};

230. Kth Smallest Element in a BST

This is the updated version of the 700, the LNR traverse is important, in BST, the LNR is the sorted ascending sequence, therefore, we can confirm the position of the kth smallest elements conveniently by gradually decreasing its value.

class Solution {
public:
int ans=0;
int kthSmallest(TreeNode* root, int k) {
help(root,k);
return ans;
}

void help(TreeNode* root, int& k){

if(root==nullptr){
return;
}

//in order l n r
//check left
help(root->left, k);

//check central
//check k and decrease?
k--;
if(k==0){
ans = root->val;
}

//check right
help(root->right, k);
}
};

Modifing tree structure

814. Binary Tree Pruning

Pruning the subtree with a particular properties. The common strategy is from bottom to up and let every subtree satisfies the requirments firstly. Be careful of the condition. If current node contains 0, and one of the child exist, it means that one of the subtree contains the 1, the current node and subtree satisfies the condition and should not be removed. The idea from bottom to up to reconstruct the whole tree is crutial for the problem that need to modify the tree structure.

class Solution {
public:
TreeNode* pruneTree(TreeNode* root) {
if (root==nullptr) return nullptr;
//the left subtree is already cleaned
//it contains 1 if the left is not nullptr
root->left = pruneTree(root->left);
//the right part is already clearned
//it contains the 1 if right is nullptr
root->right = pruneTree(root->right);
//visit current node
//if the subtree contains 1
//keep it, otherwise, delete whole tree
//or one of left or right exist, which means the subtree
//contains the 1
if (root->val == 1 || root->left || root->right){
return root;
}
//delete current node
//also delete left and right
//this function is unnecessary for result correctness
removeTree(root);
return nullptr;
}

void removeTree(TreeNode* root){
if(root==nullptr){
return;
}
//remove left
removeTree(root->left);
//remove right
removeTree(root->right);
//remove current
delete root;
}
};

More complicated trim operation, we need to adjust tree structure

The key strategy here is to consider the type of the node during the removal operation, if the removed node is leaf node or the node with one child or the node with two childern, etc. The code is more clear if considering things in this way.

669. Trim a Binary Search Tree

The operation is simple, just delete a node and adjust the tree structure. Be careful for the case discussion when we detected that the node should be removed.

class Solution {
public:
TreeNode* findLeftNode(TreeNode* root){
if(!root) return nullptr;
//if there is left node, move to the left
while(root->left){
root = root->left;
}
return root;
}

TreeNode* trimBST(TreeNode* root, int low, int high) {

if(root==nullptr) return nullptr;

//left
TreeNode* lchild = trimBST(root->left, low, high);
//right
TreeNode* rchild = trimBST(root->right, low, high);

//visit current
//if the node need to be deleted
//supposed to return if it is removed
if(root->val<low || root->val>high){
//remove node, there is bug for some case such as [1, null, 2] 2, 4
//when add this, not sure the reason
//delete root;
//leaf
if(lchild==nullptr && rchild==nullptr){
return nullptr;
}else if(lchild || rchild){
//one child
if(lchild) return lchild;
if(rchild) return rchild;
}else{
//two children
//the left tree should be the
//left side of the right tree
TreeNode* leftNode = findLeftNode(rchild);
leftNode->left = lchild;
return rchild;
}
}

//current root satisfy condition
//update left and right
root->left = lchild;
root->right= rchild;
return root;
}
};

Actually, this code can be further improved and we can notice that the case when there are two children if actaully not exist.

For example, if the current node value is c and it does not blongs to the [L,R], if c<L, all the nodes in left of the c < c < L, so all of these nodes should be removed till the current step. Similarly, when the c>R, all the right side nodes of the c > c > R, so the right side subtree should be removed before hand. This fact shows that there only exist two cases for the current recursion step, either c is the leaf node or have one side subtree.

1325 is a similar question, the constrains of removed node is more simple in this question.

450. Delete Node in a BST

The code framework and main considerations for this problem are similar with the previous one. Reuse the existing operation to deleted the selected node for the two children case is a smart point.

class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
return help(root, key, nullptr);
}

TreeNode* findMax(TreeNode* root){
while(root->right!=nullptr){
root = root->right;
}
return root;
}

TreeNode* help(TreeNode* root, int key, TreeNode*parent){

// edge case
//root is nullptr
if(root==nullptr){
return nullptr;
}

//find targeted node
if(key< root->val){
help(root->left, key, root);
}else if(key > root->val){
help(root->right, key, root);
}else{
if(root->left == nullptr && root->right == nullptr){
//case1 node is leaf node
if(parent==nullptr){
//[1] 1
delete(root);
return nullptr;
}else{
if(root->val > parent->val){
//rchild
parent->right= nullptr;
}else{
parent->left=nullptr;
}
delete(root);
}
}else if(root->left == nullptr || root->right == nullptr){
//case2 one child
if(parent==nullptr){
if(root->left){
return root->left;
}else{
return root->right;
}
delete(root);
}else{
if(root->val>parent->val){
//reset the right pointer
if(root->right){
parent->right=root->right;
}
if(root->left){
parent->right=root->left;
}
delete(root);
}else{
if(root->right){
parent->left=root->right;
}
if(root->left){
parent->left=root->left;
}
delete(root);
}
}
}else{
//case3 two children
TreeNode* leftMaxNode = findMax(root->left);
int leftMaxValue = leftMaxNode->val;
help(root->left, leftMaxValue, root);
root->val = leftMaxValue;
}
}
return root;
}
};

701. Insert into a Binary Search Tree

Using the bottom to up method and return the root of the sub tree after the modification.

class Solution {
public:
bool inserted=false;
//return the modifed tree structure
TreeNode* insertIntoBST(TreeNode* root, int val) {
//the situation to create new node and insert
//return the root
if(root==nullptr){
TreeNode* nodenew = new TreeNode(val);
inserted = true;
return nodenew;
}

if(inserted){
return root;
}

//val > current
if(val<=root->val){
TreeNode* lroot = insertIntoBST(root->left, val);
root->left=lroot;
}

//val < current
if(val>root->val){
TreeNode* rroot = insertIntoBST(root->right, val);
root->right=rroot;
}
return root;
}
};

99. Recover Binary Search Tree

This question utilizes two facts. The first is that when there is ascending sequence, there is LNR operation. Another fact is that in the ascending sequence, if we change two numbers, by checking all the elements, if there is one situation with a1>a2, we know that we switch the adjacent numbers. When there are two these cases, we can make sure that these two numbers are not at the adjacent positions.

If we do not use the fact of LNR and ascending sequence, there is C(n,2) possibilities for two numbers, this is a huge searching space.

class Solution {
public:
TreeNode* node1=nullptr;
TreeNode* node2=nullptr;
TreeNode* prev = nullptr;
void recoverTree(TreeNode* root) {
//search two points
help(root);
//the node1 and node2 should not be empty till this step
//swap two points
//only swap the value, keep the tree structure
swap(node1->val, node2->val);
return;
}

//LNR find the two that does not satisfy the ascending sequence
void help(TreeNode* root){
if(root==nullptr){
return;
}
//left
help(root->left);
//central
if(prev!=nullptr && prev->val>root->val){
//assume there are only two error node
//first one, prev position is error
//second one current position is error
if(node1==nullptr){
//printf("update node1, node1 %d node2 %d ", node1, node2);
node1=prev;
}
//if there is only one diff case
//two nodes are adjacent with each other
node2=root;
}
prev=root;
//right
help(root->right);
}
};

108. Convert Sorted Array to Binary Search Tree

This is bascially the process of reconstructing the bst tree. The bst property simplifies the code a lot. More complex one is the case that decerilize from a random case, check the 297.

class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
int len = nums.size();
return build(nums, 0, len-1);
}

TreeNode* build(vector<int>& nums,int lindex, int rindex){

if(lindex>rindex){
return nullptr;
}

//compute curr
int currindex = (lindex+rindex)/2;

//current
TreeNode* curr = new TreeNode(nums[currindex]);
//build left
TreeNode* lroot = build(nums, lindex, currindex-1);
//build right
TreeNode* rroot = build(nums, currindex+1, rindex);


curr->left = lroot;
curr->right= rroot;

return curr;
}
};

Tree + others

This type of questions use both the techniques used in tree and array (maybe map) to solve the problem. The key step here is to make sure what is the decision tree. In this blog, we only show some typical questions, such as serilization and using the map to do the accelaration. More general question that use the decision tree to do the search can be found in another article.

tree+string (serilization)

The input of the function is a string in this type of question. And it may potentially use the tree structure to derive the property of the tree structure. The difficult part is how to map the string structure into the tree structure. That is way these questions looks tricky firstly, we should first try to transform it into a tree type problem logically.

297 Serialize and Deserialize Binary Tree

The idea of this question is not complecated, but it is really error-prone. We use the layered traversal here based on the queue, be careful about the condition that when there is the mix of the nullptr node and the actual solide node. This is a little bit different with the level order question such as 429, since the null node also need to be considered if current level contains both empty and solid node

class Codec {
public:
// Encodes a tree to a single string.
// the origianl way use the layer approach
// it is also possible to use other approach
// if using the NLR
string serialize(TreeNode* root) {
string str="";
if(root==nullptr){
return str;
}
queue<TreeNode*> q;
q.push(root);
//nullnode
int levelSize = q.size();
//label if the next layer contains the solide node
//if the next layer contains no solid node, return true
bool nextcontainSolid = true;
while (q.empty()==false && nextcontainSolid){
nextcontainSolid = false;
while(levelSize>0){
levelSize--;
TreeNode *temp = q.front();
//visit node
if(temp!=nullptr){
str+=to_string(temp->val)+",";
}else{
str+="#,";
q.pop();
continue;
}
q.pop();
if(temp->left) {
q.push(temp->left);
nextcontainSolid = true;
}else{
q.push(nullptr);
}
if(temp->right){
q.push(temp->right);
nextcontainSolid = true;
}else{
q.push(nullptr);
}
}
levelSize = q.size();
}

//printf("%s", str.c_str());
return str;
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
// reconstruct based on the layered structure
if(data==""){
return nullptr;
}
// split the str based on ,
string delimiter = ",";
int delimLength = delimiter.length();
int posStart=0;
int posEnd=0;
TreeNode* root = nullptr;
TreeNode* parent = nullptr;
queue<TreeNode*>q;
int index=0;
while ((posEnd = data.find(delimiter,posStart)) != string::npos) {
string token = data.substr(posStart, posEnd-posStart);
//check the element
//printf("<%s>", token.c_str());
//constructure by layered way
if(root==nullptr){
//the first element
root = new TreeNode(stoi(token));
q.push(root);
}else{
if(index%2==0){
//update the parent
//when the current left and right are built ok
parent = q.front();
q.pop();
}

// construct node
// the parent is root for the first case
TreeNode* current=nullptr;
if(token!="#"){
current = new TreeNode(stoi(token));
//printf("curr %d parr %d ", current->val, parent->val);
}

// left or right separately
if(index%2==0){
parent->left = current;
}else{
parent->right = current;
}

// node is not null
// push node into the queue
if(current!=nullptr){
q.push(current);
}
index++;
}
posStart=posEnd+delimLength;
}
return root;
}
};

The similar one is the 449, we can also use the similar level traversal techniques. Is there more efficient techniques for the bst structure?

tree+map or dp (using map to optimize the code)

Some complex path sum questions may use the map, such as the 437. The main idead that uses the map is to improve the performance of the searching.

337. House Robber III

This one is inspiring. There is some intersection between the traditional tree based strategy such as top to bottom or bottom to up with the thinking perspective of the dp.

For example, this is the code from the top to bottom. We make sure the status of the start node (parent node) and then considering the status of the child node.

class Solution {
public:
// 1 index of the node, 2 true or false
map<TreeNode*, map<bool, int> > cache;
int rob(TreeNode* root) {
//choose root
int max1=help(root,true);
int max2=help(root,false);
return max(max1,max2);
}
// return the max value when the current node is root
int help(TreeNode* root, bool ifrob){
if(cache.find(root)!=cache.end()){
if(cache[root].find(ifrob)!=cache[root].end()){
return cache[root][ifrob];
}
}

if(root==nullptr){
return 0;
}
// add a cache here?
if(ifrob){
int lvalue=help(root->left,false);
int rvalue=help(root->right,false);
return lvalue+rvalue+root->val;
}

//if current is false
//the next level can be false or true
int l1=help(root->left,false);
int l2=help(root->right,false);
int l3=help(root->left,true);
int l4=help(root->right,true);

int result = max(l1,l3)+max(l2,l4);

cache[root][ifrob]=result;

return result;
}
};

and this is the code from the bottom to up. We make sure the status of the child node and then refer to the status of the parent node.

class Solution {
public:
int rob(TreeNode* root) {
if(root==nullptr){
return 0;
}
int Vr, Vnr = 0;
helper(root, Vr, Vnr);
return max(Vr,Vnr);
}

//return value is the status of the current
//The Vcr and Vcnr are used to store the intermediate status
void helper(TreeNode* root, int& Vcr, int& Vcnr){
if(root==nullptr){
Vcr = 0;
Vcnr = 0;
return;
}

//l child status
int Vlr, Vlnr =0;
helper(root->left,Vlr,Vlnr);

//r child status
int Vrr, Vrnr =0;
helper(root->right,Vrr,Vrnr);

//compute the Vcr and Vcnr
//if current rub
Vcr = Vlnr+Vrnr+root->val;
//if current not rub
Vcnr = max(Vlr,Vlnr)+max(Vrr,Vrnr);
return;
}
};

If we consider the issue from the status transfer, the parent node and the child node mainatins a kind of relationship (depending on the context of the question), the status table is listed as follows from the child to the parent

L R C
R NR NR
R R NR
NR NR R/NR
NR R NR

we could check the parent firstly or child firstly, there are two different programming paradigm. For the first version, we use the strategy from start to the end. For the second case, we fix the status of the leaf node firstly, then derive it from the bottom to the top. Even for previous questions that search the properties of the tree, we also use the similar ideas. These questions only have one variable and the status is also comparatively simple.

Inspired by the dp solution of the 337, we can write another dp solution of the 968. Binary Tree Cameras:

class Solution {   
public:
int ans=0;
int minCameraCover(TreeNode* root) {
//root is null
if(root==nullptr){
return 0;
}

//at least two layers
int Vcm, Vncm, Vncnm=0;
helper(root, Vcm, Vncm, Vncnm);
//the result is 1 at least
if(Vcm==0){
return Vncm;
}
if(Vncm==0){
return Vcm;
}
return min(Vcm,Vncm);
}

//when it is not at the top position, we can always postpone the choice
void helper(TreeNode* root, int& Vcm, int& Vncm, int& Vncnm){

//null
if(root == nullptr){
//the init status should be fixed, which is ncm
Vcm=9999;
Vncm=0;
Vncnm=9999;
return;
}

int LVcm, LVncm, LVncnm=0;
helper(root->left, LVcm, LVncm, LVncnm);
int RVcm, RVncm, RVncnm=0;
helper(root->right, RVcm, RVncm, RVncnm);

Vcm = 1+min(LVcm, min(LVncm, LVncnm))+min(RVcm, min(RVncm, RVncnm));
Vncm= min(LVcm+RVcm, min((LVcm+RVncm), (LVncm+RVcm)));
Vncnm=min(LVcm,LVncm)+min(RVcm, RVncm);

return;
}
};

This code is easy to understand if we list the status transfer between children and the parent:

L——R——C
CM CM CM/NCM/NCNM
CM NCM CM/NCM/NCNM
CM NCNM CM
NCM CM CM/NCM/NCNM
NCM NCM CM/NCNM
NCM NCNM CM
NCNM CM CM
NCNM NCM CM
NCNM NCNM CM

The tricky point is the status when there is nullptr, at that case, we should assume the node status is the NCM. For the origianl solution, it assume that when there is CM or NCM, it is always prefered to postpone the camera except the current node is the top layer, so we can guarantee the status of the tree by this analysis. But the dp solution is a more general case.

推荐文章