Recursion



698
  Note this is similar to DFS problem 473 Matchsticks to Square. The partition problem is NP-Complete.
 Base Case:
 if (k <= 0 ||  sum % k != 0) return false
Call  helper function: canPartition(nums, visited, 0, k, 0, sum / k);
bool canPartition(vector<int>& nums, vector<bool>& visited, int start_index, int k, int cur_sum, int target) {}
  Base case for helper:
        if (k == 1)
            return true;

  if (cur_sum == target)  recursively call the helper with decreased k value by 1
            return canPartition(nums, visited, 0 /*reset to 0*/, k - 1, 0, target);

 Otherwise, for loop each number in the array, if not visited, mark it as visited and recursively call the helper canPartition with updated cur_sum and cur_num and increased start_index value. if any partition succeeds, return true. Otherwise, unmark the current num in the flag array and try next number.



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 (^ form)

Implementation:
        int leftLUP = longestUnivaluePath(root->left);
        int rightLUP = longestUnivaluePath(root->right);
        int leftDepth = univalueDepth(root->left, root->val);
        int rightDepth = univalueDepth(root->right, root->val);
        return max({leftLUP, rightLUP, leftDepth + rightDepth});

int univalueDepth(TreeNode* root, int val) {
        if (!root || root->val != val)
            return 0;
       
        return max(univalueDepth(root->left, val), univalueDepth(root->right, val)) + 1;
    }
    


894
Let \text{FBT}(N) be the list of all possible full binary trees with N nodes.
Every full binary tree T with 3 or more nodes, has 2 children at its root. Each of those children left and right are themselves full binary trees.
Thus, for N \geq 3, we can formulate the recursion: \text{FBT}(N) = [All trees with left child from \text{FBT}(x) and right child from \text{FBT}(N-1-x), for all x].
Also, by a simple counting argument, there are no full binary trees with a positive, even number of nodes.
Finally, we should cache previous results of the function \text{FBT} so that we don't have to recalculate them in our recursion.

Comments

Post a Comment

Popular posts from this blog

zhitongguigu

Lecture 1: To do: (117? 199) Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree . In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree. numerical_limits<int>::min()   <==> INT_MIN
Read more

Array Part2

Two pointers 977 Squares of a Sorted Array      We can use two pointers to read the positive and negative parts of the array - one pointer  j  in the positive direction, and another  i  in the negative direction. Now that we are reading two increasing arrays (the squares of the elements), we can merge these arrays together using a two-pointer technique. 11 Container With Most Water      O(N) time and O(1) space, since better candidadates must use the taller line of l and r therefore we can use two pointer keep moving towards each other until they meet. Always abandon the shorter line while moving. 80 Remove Duplicates from Sorted Array II      tail = 0; for (int i = 0;  i < nums.size(); i++)           if (i < 2 || nums[i] > nums[tail - 2]) // not included twice yet                 nums[tail++] = nums...
Read more

Two pointers (Part 1)

344 Reverse String      Use two pointers i, j. keep switching elements at position i, j while i < j.     string reverseString(string s) {        for (int i = 0, j = s.size() - 1; i < j; i++, j--)            swap(s[i], s[j]);                  return s;     } 345 Reverse Vowels of a String      Similar with 344  Reverse String ,  except we need to guard the swap operation conditionally based on whether the current two chars are vowels or not. 283 Move Zeroes      Use two pointers, the front iterates the elements in the array. while the tail one keeps the current store position. If front is not zero, store it to the tail position and increase tail pointer. After the loop, set all the remaining with zero. 349 Intersection of Two Arrays      ...
Read more