Leetcode 257: Binary Tree Paths

 https://leetcode.com/problems/binary-tree-paths/description/

Notes:

This question is a typical warm-up question in the interview. So the key is to get it done clearly and quickly. (and bug-free)

Since it is a tree, so recursion is the first choice. 

And it requests to print the path, so dfs is a better choice (than bfs). 

Then ending condition (base case) is when the node is a leaf (both left and right are null).

A hidden ending condition is when the current node is null.

See the code below:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        dfs(root, "", res);
        return res;
    }
private:
    void dfs(TreeNode* r, string s, vector<string>& res) {
        if(!r) return;
        if(!r->left && !r->right) res.push_back(s + to_string(r->val));
        dfs(r->right, s + to_string(r->val) + "->", res);
        dfs(r->left, s + to_string(r->val) + "->", res);
    }
};

Leetcode 508: Most Frequent Subtree Sum

https://leetcode.com/problems/most-frequent-subtree-sum/description/

Notes:

We need a  hash table to count the frequencies of each possible sum. Once we have this information, then we can easily find the one(s) with the maximum frequency.

So the problem becomes how to effectively find the sum of all the subtrees.

Bottom-up recursion method would be a good choice: if we have calculated the sums of both the left and the right parts, then we just need to add them with the value of the root to get the total sum of the this sub-tree. Bottom-up recursion naturally gives the sums of all the subtrees in the tree.

The T-C is O(N), and the S-C is O(N) too. N is the number of nodes in the tree.

See the code below:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        vector<int> res;
        ct = 0;
        dfs(root);
   //     cout<<ct<<endl;
        for(auto &a : mp) {
            if(a.second == ct) res.push_back(a.first);
        }
        return res;
    }

private:
    unordered_map<int, int> mp; //<sum, count>
    int ct;
    int dfs(TreeNode* r) {
        if(!r) return 0;
        int a = dfs(r->left), b = dfs(r->right), sum = a + b + r->val;
        ct = max(ct, ++mp[sum]);
        return sum;
    }
};

Leetcode 979: Distribute Coins in Binary Tree

https://leetcode.com/problems/distribute-coins-in-binary-tree/description/

Notes:

This question can be solved by recursion, which is usually employed for tree questions.

One way to think is using post-order recursion.

First of all, we need to figure out what should be returned. It should be the coins number from the left  + right + root->val - 1. Minus 1 because we need to keep one at root.

Then next, we should to ask: what is the moves required? If there are more coins than needed in a subtree, we need to move; but if there are less than needed, we also need to move!

Thus, we need to calculate the absolute values for the number of moves.

See the code below:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    int distributeCoins(TreeNode* root) {
        res = 0;
        helper(root);
        return res;
    }

private:
    int res;
    int helper(TreeNode* root) {
        if(!root) return 0;
        int l = helper(root->left), r = helper(root->right);
        res += abs(l) + abs(r);
     //   cout<<res<<endl;
        return l + r + root->val - 1;
    }
};

Leetcode 1145: Binary Tree Coloring Game

https://leetcode.com/problems/binary-tree-coloring-game/description/

Notes:

The description above is not clear actually. Basically it says two players A and B will play alternatively and optimally. A pick up X first, then it will be B's turn to pick up any one of the remaining nodes. After that, it backs to A's turn to pick one.

Now A cannot choose any one he likes: he has to choose a): it is not picked (colored) yet; b): it must be the neighbor of his previously picks (or the same color). It can be either the left-kid, right-kid, or the parent. After that, it is B's turn and B follows the same rule.

The key observation is that: After the A player pick up x, then B player need to choose maximum of three cases: the left-kid subtree, right-kid subtree, or on the x parent side. If B always play optimally, B will choose the maximum of the three cases.

Then B will color or pick all the nodes in that subtree, since A cannot cross over. Similarly, B cannot cross over to the rest part of the tree. And all the rest nodes will be picked or colored by A.

If the maximum of three cases is larger than n/2, then B will win.

It is relative easier to calculate the number of nodes in the left-kid subtree and right-kid subtree than that on the parent side. However, we know the total is n, thus, when the left and right parts are calculated, then the rest part will be (n - left - right - 1).

See the code below:

/*
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    bool btreeGameWinningMove(TreeNode* root, int n, int x) {
        int lt = 0, rt = 0;
        dsf(root, lt, rt, x);
        return max(max(lt, rt), n-lt-rt-1) > n/2;
    }
private:
    int dsf(TreeNode* r, int &lt, int &rt, int &x) {
        if(!r) return 0;
        int left = dsf(r->left, lt, rt, x), right = dsf(r->right, lt, rt, x);
        if(r->val == x) {
            lt = left;
            rt = right;
        }
        return left + right + 1;
    }
};

The follow up question:

Let say A will pick up first and can pick up any node he likes. Then the question is that: is there a node that A can pick up or color firstly to guarantee that he will win eventually? If yes, output all these nodes that can be chosen as the first node for A.

class Solution {
public:
    bool btreeGameWinningMove(TreeNode* root, int n, int x) {
        vector<int> vs;
        dsf(root, n, x, vs);
        return vs;
    }

private:
    int dsf(TreeNode* r, int &n, int &x, vector<int> &ns) {
        if(!r) return 0;
        int left = dsf(r->left, n, x, vs), right = dsf(r->right, n, x, vs);
        if(max(max(left, right), n-left-right-1)) <= n/2 ) vs.push_back(r->val);
        return left + right + 1;
    }
};

LeetCode 156: Binary Tree Upside Down

https://leetcode.com/problems/binary-tree-upside-down/


Notes:
For tree-related questions, we usually can think about recursion. To this question, one way to think about it is that if we can finish f(root->left), then we just need to set root->left->right to the root, root->left->left to the root->right. and set root->left = NULL, and root->right = NULL. Done.

This is a bottom-up recursion.

See the code below:

class Solution {
public:
    TreeNode *upsideDownBinaryTree(TreeNode *root) {
        if (!root || !root->left) return root;//base case
        TreeNode *l = root->left, *r = root->right;
        TreeNode *res = upsideDownBinaryTree(l);
        l->left = r;
        l->right = root;
        root->left = NULL;
        root->right = NULL;
        return res;
    }
};

A second way to solve this problem: iterative scan in a top-down fashion. Actually it is very similar to reverse a LinkedList.

See the code below:

class Solution {
public:
    TreeNode *upsideDownBinaryTree(TreeNode *root) {
        TreeNode *cur = root, *pre = NULL, *next = NULL, *tmp = NULL;
        while (cur) {
            next = cur->left;
            cur->left = tmp;
            tmp = cur->right;
            cur->right = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};