Algorithm(8) Naive Tree(By input data structure)

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).

• (8) Sth that might be asked in the interview is actually the multi order tree or the tree with multiple children. The thought can be limited if only considering the tree with two branch. One typical question is to build a index that can find a min value in specific sub range of array. In this case, we might have multiple segment, we store the min value of each segment, the min value of whole array is must one of the these subrange, then we just find the one that is minimal in this subrange, we can even sort each level of children to accelarate the searching process. The multiple node tree can be the founudation of B tree, these question might be asked in practical interview. The start point is find an element in specific range, then move to the harder one. The complicated idea of b tree than multi-branch tree is how to make each node more balanced and split the node. The key idea behind the index is just remember the search path as it is, not the searching operation itsself. (When we search it, we build it and then we can reuse this index tree)

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?

Tire tree or dict tree for accelaration

The 212 is a good exmaple, we need to do the similar search operations for multiple times, it can save time if we first trasfer the original structure into a tired tree for accelarating searching process to avoid the redouantant searching. The idea is to extract the common part of the tree. Look at more details for the details in the search part.

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.