Tree Summary

Tree Traversal

(1)  Pre-Order, In-Order, Post-Order (recursion and iterative)
       144  Binary Tree Preorder Traversal
         Iterative: Using a stack, push the root into stack first. While the stack is not empty. pop and
         visit the top node. If the right (note here we push the right before left, so when pop, we will
        visit left before right) child is not NULL,  push the right child into stack. If the left child is
        not NULL, push the left into stack. Keep doing this until all the nodes are visited.

(2)   173 Binary Search Tree Iterator
    This problem is actually Iterative inOrder traversal
     maintain a  pushLeft function and a data member stack<TreeNode*> st. Call pushLeft in
     the constructor BSTIterator. And hasNext() is just check the stack is not NULL. next() is
     just visit st.top() element. But in order to visit the right child, we have to pushLeft(p->right)
    before return p->val. It is a good idea to use pushLeft function in inOrder Traversal.

(3) 94 Binary Tree Inorder Traversal
      (a)  Recursive:  DFS(root->left, res), res.push_back(root->val), DFS(root->right, res);
      (b) Iterative:  (b.1) Use a stack st to do this. Define p and initialize it to root. While p is not NULL and the stack st is not empty(), do the following.  (b.2) while p is not NULL, keep push p into the stack and let p = p->left. (b.3) after b.2, check if the stack is not empty. If so, visit the top element and pop it and let p = p->right.

(2)  Level Order:
      102   Binary Tree Level Order Traversal
               BFS: queue + keep a nextLevelStarter pointer to track where is the first node in each level
               DFS: pass over the vector<vector<int> >& res array and depth, when res.size() == depth,
                         Create a new vector<int>() and push into res. Otherwise when res.size() > depth,
                         res[depth].push_back(root->val). Must use pre-order traversal.
   

107	Binary Tree Level Order Traversal II

       Similar as above: except one extra step: return vector<vector<int> > (res.rbegin(), res.rend())

       BFS: Define a queue, push root in queue. loop each element while q is not empty, define
       a  nextLevelStarter to keep track of the beginning node of each level. Loop the level for that
       level while q is not empty and nextLevelStarter is not equal the front element in queue.
      Update nextLevelStarter with either p->left or p->right if it is nullptr. Push non-empty left
      node and  right node into the queue. When exit the inner loop, push the nodes in the current
      level into result.

       515  Find Largest Value in Each Tree Row   
             BFS: Same with 102, instead of keep all values, just keep the max value while level traversal.
             DFS:  pass over the vector<int>& res array and depth, when res.size() == depth,
                         push root->val into res. Otherwise when res.size() > depth,
                         res[depth] = max(res[depth], root->val).

        513   Find Bottom Left Tree Value
        (a) level traversal and return the last non NULL nextLevelStarter->val;

         (b) Pass around a reference of the maxDepth parameter. Update its value
              whenever we first enter a new level of depth while  DFS traversal and
              save that first node val. Return the last saved node val.

       637. Average of Levels in Binary Tree
        calcuate size = q.size()  and use that as the trip count for inner loop, inside the inner loop
        for each level pop front node and add value to the sum. After exit inner loop calculate the
        average in the outer loop and push_back the average of current level to the result vector

       199  Binary Tree Right Side View
        (a) Level order traversal, define last element in the outer loop, keep it updated in the inner, when
        exit inner loop and enter outer loop, push_back into the result vector.
        (b) Could be solved using DFS (visit the right tree before the left tree) with two
            parameters passed around   vector<int> res, int level.  res.push_back(root->val) when
            level ==  res.size()

(3)  Zig-Zag Level Order:

Construct:

(1) 106     Construct Binary Tree from Inorder and Postorder Traversal
      (a) Find index of root in the inorder list.
       TreeNode* root = new TreeNode(inorder[index]);
        root->left = constructTree(inorder, inBegin, index - 1,
                                   postorder, postBegin, postBegin + (index - 1 - inBegin));
        root->right = constructTree(inorder, index + 1, inEnd,
                                   postorder, postEnd - 1 - (inEnd - index - 1), postEnd - 1);
(2) 105    Construct Binary Tree from Preorder and Inorder Traversal
        (a) Find index of root in the inorder list.
        TreeNode* root = new TreeNode(preorder[preBegin]);
        (b) root->left = constructTree(preorder, preBegin + 1,  preBegin + 1 + (index - 1 - inBegin),
                                   inorder, inBegin, index - 1);
             root->right = constructTree(preorder, preEnd - (inEnd - index - 1),  preEnd,
                                   inorder, index + 1, inEnd);


(3) 606    Construct String from Binary Tree
If t is NULL return "" string
If t is childless node, return to_string(t->val)
Otherwise:
       add the t->val,
       add the left tree string unconditionally
       add the right tree string only when it is not NULL

(4) 536    Construct Binary Tree from String

(5) 654. Maximum Binary Tree
     Similar to construct BST from sorted array, except the input array
     here is not sorted. We have to loop each element to find the max
     value and then recursively construct the left tree and right tree
     using the elements before maxIdx and after maxIdx.

(6) 655. Print Binary Tree
     get the height of the tree as the res array first dimension size and get the full tree size for the given
     tree as the width or the second dimension size (since we may need to print a full tree).
     initialize vector<vector<string> > ans = vector<vector<string> > (height,  vector<string>
     (width, ""); and then like the other problem above. We can recursively print the root->val
     with ans[level][mid] = root->val, and the left tree with nodes from left to mid - 1 and right
     tree with node from mid + 1 to right. (Don't forget to pass the current level while recursion)

Convert Tree:

(1) 108    Convert Sorted Array to Binary Search Tree
                use the mid = begin + (end  - begin) / 2 as the root, and the elements from begin to mid -1
                as the left child and the element from  mid+1 to end as the right child, it will be a
                height-balanced binary tree (since left and right child has at most one different number of
                 node
     
(2)   109      Convert Sorted List to Binary Search Tree
                    (a)  Convert to array and use the same solution in 108
                    (b)  If convert directly,  the only difference between construct tree from array and from
                          linked list, is the way to access the mid node. For array we direct access using index
                          arr[mid], while linked list need to start from head (index 0) and move forwad mid
                          steps to access the mid node. Other than that, the code is similar with convert sorted
                          array to binary search tree.

  (3)    538    Convert BST to Greater Tree
                     idea: reverse in-order traversal (keep a global sum val or pass it as ref)

 

Validate Tree

(1)		Same Tree A.root->val == B.root->val && isSame(left) && isSame(right)

 (2).      Validate Symmetric Tree:
                   (a) Recursion:
                    (t1->val == t2->val) && isMirror(t1->left, t2->right) && isMirror(t1->right, t2->left)

                   (b) Iterative using stack
                   push left->left with right->right for comparison at pop
                   push left->right with right->left for comparison at pop


 (3).       Validate BST
             // get the first in order node of the right child  and make sure it is larger than root->val
             // get the last in order node of the left child and make sure it is smaller than root->val
               
 (4).      Validate Balanced Binary Tree:
             Recursion:  (abs(height(left)-height(right)) <=1) && isBalanced(left) && isBalanced(right)

Tree Depth

(1).        104. Maximum Depth of Binary Tree
               max(maxDepth(root->left), maxDepth(root->right)) + 1;  // DFS
               level traversal with count++ for each level          // BFS
(2)          111 Minimum Depth of Binary Tree
               Similar to max Depth of BT, but be careful about the left/right child NULL special cases.

Tree Path Sum

(1).  112  Path Sum
        if (!root->left &&  !root->right && root->val == sum) return true;
        hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val)

(2).  113 Path Sum II
         (a) backtracking, keep the cur node list for traversing, push to the result when reach the leaf
          and satisfy conditions, no matter satisfy or not satisfy the condition pop the last element        (backtrack when return from the current level to its caller), DFS.
         (b) You could also don't pop_back() cur, if you pass value of cur (instead of reference) instead.
       

(3).  437 Path Sum III
         return DFS(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
         i.e. foreach each node and do the DFS in Path Sum II

(4).  666 Path Sum IV
     

(5).  404  Sum of Left Leaves
       pass around a parameter isLeft (which is set to true for all left child and false for all right child)
       and for NULL node return 0, for leaf node (left leaf) add it to sum. Recursively call the left child
       and the right child. Return sum at the end.

(6).  129. Sum Root to Leaf Numbers
               preOrder traversal :  preSum = preSum * 10 + root->val;
               return DFS(root->left, preSum) + DFS(root->right, preSum);

(7).  124 Binary Tree Maximum Path Sum
               DFS return side max value (left or right): pass in maxPS  during traversal,
              maxPS =  max(maxPS, left + right + root->val)

(8).  508 Most Frequent Subtree Sum
               Hash map combined with DFS.
               Keep a map which saves the current subTree sum  and its frequency. Also update the max
               frequency while recursion.  After DFS recursion, in another loop put the max frequency
               node value into the vector result and return it.

(9).  653 Two Sum IV - Input is a BST
               unordered_set combined with DFS

Common Ancestor

 (1).   235 Lowest Common Ancestor of a Binary Search Tree
         if both p and q are less than the root->val, recursively search the left sub-tree.
         if both p and q are great than the root->val, recursively search the right sub-tree.
         Otherwise, the LCA is the root
 (2).   236 Lowest Common Ancestor of a Binary Tree
          Similar to above, but instead of using BST  property. Using isSubTree(root->left, p, q)
          and isSubTree(root->right, p, q) to decide whether the two nodes are both in the left or right
          side. If not, then return the root.

Binary Search Tree

 (1).   108.  Convert Sorted Array to Binary Search Tree

         root->left = toBST(nums, begin, mid - 1);
          root->right = toBST(nums, mid + 1, end);

(2).     98.   Validate Binary Search Tree

          leftMostOfRightTree < root->val &&
             rightMostOfLeftTree > root->val   &&
             isValidBST(root->left) && isValidBST(root->right)

(3).     669. Trim a Binary Search Tree
           if (root->val < L) return trimBST(root->left)
           else if (root->val > R) return trimBST(root->right)
           else { root->left = trimBST(root->left);  root->right = trimBST(root->right);  return root;}

(4).     Find Mode in Binary Search Tree
inOrderTraversal + hashMap to save the frequency of all vals and the maximum frequency.  Iterate all hashMap to save the maximum frequency element  (i.e. the modes) into the vector


(5)         99.   Recover Binary Search Tree

// Solution 1: put the TreeNode elements into a vector, sort them and compare them with the unsorted.
// at he first different point are the two swapped nodes. swap their values.

// Solution 2: record the two elements during inOrder traversal and swap their values after.
             
(6).      96.        Unique Binary Search Trees

                         O(N^2) DP:  (1) Memoization. (2) Iteration.
                         Stupid brutal force O(2^N) TLE

(7).        95.        Unique Binary Search Trees II

Recursively construct all the possible left tree (returns vector<TreeNode*>) and all the possible right tree. And outer for loop left trees and inner for loop right trees to construct all the unique trees.
                     

No Access:
（8)    272.    Closest Binary Search Tree Value II 

No Access:
(9).  270.    Closest Binary Search Tree Value 

Find in Tree

(1).  652      Find Duplicate Subtrees

        construct a string to vector of TreeNode map. If there is duplicated trees,
        then the corresponding map element second size (vector size) is great than 1.
        Push all elements satisfy that in the result map and return.

 (2).  515      Find Largest Value in Each Tree Row

                   Just keep the max value while level traversal.

(3).  513       Find Bottom Left Tree Value
                     BFS: Level Traversal, return the last nextLevelStarter value
                     DFS: keep track of the maxDepth, depth, leftVal, whenever the current depth is
                              greater than maxDepth, update maxDepth and leftVal (cur node val)

(4).  501       Find Mode in Binary Search Tree
                    InOrder traversal to collect the (1) maxCount (mode)  (2)  each element and its
                   count /frequency  in a map.  loop again to put the element value of modes into the result
                   vector and return it.

(5).  366       Find Leaves of Binary Tree. (locked)

Redundant Connection (1).  684.        Redundant Connection

                         Union find algorithm for disjoint set.
                        See Union Find algorithm for disjoint set (并查集算法）

   (2).  685.       Redundant Connection II (hard)

Complete Tree

222 Count Complete Tree Nodes 

This problem can be solved in O(N) time using DFS (preOrder/InOrder/postOrder) or BFS (level traversal using queue). But they both TLE. Clearly, the problem needs some algorithm more clever which utilize the complete tree property.

Note 1: the height of a complete tree is the left most tree node, we get the the height of a complete tree in O(lgN) time. 


Note 2: for any  given complete tree. At least one of the left and the right sub-tree is full binary tree. If the height of the left tree is equal to the height of the right tree, then the left tree must be full tree. Else if the height of the left is NOT equal (great than actually) to the height of the right tree. Then the right tree more be full tree. 


Note 3:  For a given full tree, its nodes  number is 2^height - 1 (single node is count as height 0).


Therefore we could count the total number nodes of a complete tree in O(lgN) time recursively:

       int lh = completeTreeHeight(root->left);
       int lr = completeTreeHeight(root->right);
        
        if (lh == lr) // left tree must be full tree, and right treee may not
            return (1 << lh) + countNodes(root->right);
        else // right tree must be full tree, and left tree may not
            return (1 << lr) + countNodes(root->left);

Serialize Tree

449  Serialize and Deserialize BST

     Use preOrderDFS to serialize. Burn the integer into 4 chars and push_back

     it to the string. And recursively do the same thing for the left and right

     tree.

     For deserialize, keep the pos to access the buffer that contains the integers

     in form of chars and minValue and maxValue. Construct root and move pos by 

     sizeof(int) and recursively construct the left and right tree. Note if the

     root->val is great than maxValue or it is less than minValue that means you

     reached a node in a different sub-tree, return NULL.

     We have to use the following for serialize:

     memcpy(buffer, &root->val, sizeof(int));
     for (int i = 0; i < 4; i++) order += buffer[i]; 

     and use the following for deserialize:

     memcpy(&val, &buffer[pos], sizeof(int));

     pos += sizeof(int);

     Otherwise, it only works for single digit values (if you save int and recover 

     int directly) 

 652.  Find Duplicate Subtrees
          Recursively serialize the tree nodes into a string and create a map from the string to the tree root. After that, push_back the map element whose second size great than one (meaning there is duplication) into the result and return.

Subtree

(1)      652.  Find Duplicate Subtrees (see above : Serialize Tree)

(2)       572 Subtree of Another Tree

Solution 1 : serialize both trees into two strings and check whether one is the substring of another
Solution 2:   Check isSameTree(s,t) , if not recursively call isSubTree(s->left, t) and
                     isSubTree(s- >right, t)


(3).         508.   Most Frequent Subtree Sum

               Hash map combined with DFS.
               Keep a map which saves the current subTree sum  and its frequency. Also update the max
               frequency while recursion.  After DFS recursion, in another loop put the max frequency
               node value into the vector result and return it.

Smallest Element

   671. Second Minimum Node In a Binary Tree

    use a helper function to pass around two values: minVal and nonRootMinVal (i.e secondMinVal)
    which are initialized to roo->val and INT_MAX. Use preOrder DFS traversal to recursively update
    nonRootMinVal = min(nonRootMinVal, root->val) when it is not equal to minVal.

  230  Kth Smallest Element in a BST
     (a) Pass a count value to in order DFS traversal and keep increase it until hit the kth element
    and save that value in the out parameter and return.    O(N) time complexity

   (b) CountNodes of left tree and utilize BST property to do binary search, this is still not
       O(lgN)  since the coutNode function is still O(N)

   (c). Build a TreeNodeWithCount data structure for each node in O(N) time then the future
         search and insert / delete could be done in O(lgN) time which is suitable for
         frequently query/insert/delete in the tree

         After the TreeNodeWithCount is built in O(N) time. For future search and insert delete we can
         do :
         (c.1) If left is not NULL
                        if (rootWithCount->left->count >= k)
                              return kthSmallest(rootWithCount->left, k);
                        else if (rootWithCount->left->count == k - 1)
                              return rootWithCount->val;
                        else // rootWithCount->left->count  < k -1
                              return kthSmallest(rootWithCount->right, k - rootWithCount->left->count - 1)
       (c.2)  Else left is NULL
                         if (k == 1)
                              return rootWithCount->val;
                         else
                              return kthSmallest(rootWithCount->right, k  - 1)
                  

Refactor/Restruct Tree

226.  Invert Binary Tree

Invert the left tree and then invert the right tree and switch the left and right pointer of root


 669. Trim a Binary Search Tree
           if (root->val < L) return trimBST(root->left)
           else if (root->val > R) return trimBST(root->right)
           else { root->left = trimBST(root->left);  root->right = trimBST(root->right);  return root;}


450.   Delete Node in a BST   
Recursively find the node that has the same value as the key, while setting the left/right nodes equal to the returned subtree
Once the node is found, have to handle the below 4 cases
node doesn't have left or right - return null
node only has left subtree- return the left subtree
node only has right subtree- return the right subtree
node has both left and right - find the minimum value in the right subtree, set that value to the currently found node, then recursively delete the minimum value in the right subtree

623. Add One Row to Tree
        BFS level traversal using two queues, to get the elements at (d - 1) level. And then
        insert the elements as requested.

617.  Merge Two Binary Trees
        Tree cases:
         (a) if (!t1) return t2;
         (b) if (!t2) return t1;
         (c) Otherwise (i.e. both t1 and t2 are not NULL)
               t1->val += t2->val.
               t1->left = mergeTree(t1->left, t2->left)
               t1->right = mergeTree(t1->right, t2->right)

Longest Path 

687  Longest Univalue Path

The longest univalue path is from one of the three cases:
(a)  longestUnivaluePath(root->left)
(b)  longestUnivaluePath(root->right)
(c)  the longest univalue path that use tree root->val

543. Diameter of Binary Tree (i.e. Longest Path any value)
The longest path is from one of the three cases:
(a)  longestPath(root->left)
(b)  longestPath(root->right)
(c)  the longest path that pass through the tree root (do not need check val == root->val)

Tree to Linked List

116  Populating Next Right Pointers in Each Node
BFS: Level Order Traversal: Trivial
DFS O(1) space, set root->right = root->next->left when cross subtree
for root. Recursively call connect(root->left) and connect(root->right)
This is safe to do since we already have the root->next connected before
going to the child nodes.


Populating Next Right Pointers in Each Node II
Similar with 116, but need to use findNext(root->next) function to get the next element to be connect
to the current node.

114 Flatten Binary Tree to Linked List
preOrder traversal to populate a vector<TreeNode*> with all
tree nodes. In a for loop, set all the left child to NULL and
set the right child to point to its  successor in the vector

Other:

563  Binary Tree Tilt
return root ? abs(sumOfTree(root->left) - sumOfTree(root->right)) + findTilt(root->left) + findTilt(root->right) : 0


257.  Binary Tree Paths 

keep the curStr in preOrderDFS, when reach a leaf node push back the curStr to the
 vector<string> res.

337 House Robber III  
return max(root->val + rob(ll) + rob(lr) + rob(rl) + rob(rr), rob(l) + rob(r));
Using ordered_map<TreeNode*, int> to save temporary result to avoid repeated calculation.



662   Maximum Width of Binary Tree
The main knowledge that uses here is the one-dimension array representation of
Binary tree. e.g: if you have an binary tree preOrder [1,2,4,5,3,6,7] inOrder
[4,2,5,1,6,3,7].  The 1-D representation will be [1,2,3,4,5,6,7] (note here n starts
with one). In this 1-D representation, if the parent node position is n, then the
left child postion is 2*n, and the right child position is 2*n + 1
   
        return max({(pos - start[level] + 1),
                             DFS(root->left, start, 2 * pos, level + 1),
                             DFS(root->right, start, 2 * pos + 1, level + 1)});

树分类 【他山之玉】

https://dyang2016.wordpress.com/2016/10/15/tree%E7%9A%84%E6%80%BB%E7%BB%93/
树总结

http://blog.csdn.net/qqxx6661/article/details/76223475