今天的題單：

• Subtree of Another Tree

• Squares of a Sorted Array

572. Subtree of Another Tree

思路：在 binary tree 中可能有很多 node 的值和 target subtree 的 node 一樣，這些 node 都可以是 sub-tree 的 root，因此作法分成兩步驟:

1. 找出所有可能的 root

2. 一個一個檢查以此 node 形成的 subtree 是不是跟 target subtree 相同，只要有一個是就返回 true

/**
 * 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:
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        TreeNode* head = nullptr;
        stack<TreeNode*> stk;

        // find all the possible roots in the tree
        findSubtreeRoot(root, subRoot->val, stk);
        
        // Check the all possible sub-tree
        while (!stk.empty()) {
            if (sameTree(stk.top(), subRoot)) {
                return true;
            }
            stk.pop();
        }
        return false;
    }

    void findSubtreeRoot(TreeNode* root, int target, stack<TreeNode*>& stk) {
        // DFS
        if (root == nullptr) return;
        if (root->val == target) {
            stk.push(root);
        }
        findSubtreeRoot(root->left, target, stk);
        findSubtreeRoot(root->right, target, stk);
    }

    bool sameTree(TreeNode* root1, TreeNode* root2) {
        if (root1 == nullptr && root2 == nullptr)
            return true;
        if (root1 == nullptr || root2 == nullptr)
            return false;
        return root1->val == root2->val && sameTree(root1->left, root2->left) && sameTree(root1->right, root2->right);
    }
};

977. Squares of a Sorted Array

思路：找到非負整數的分界線，把 list 分成兩半，應用 merge sort 的方式把數字的平方排序到新的陣列裡，此方法是 O(n) time。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> sorted_nums;

        int i = 0;
        int j = 0;

        while (j < nums.size() && nums[j] < 0) {
            j++;
        }

        i = j - 1;

        while (i >= 0 || j < nums.size()) {
            if (i < 0) {
                sorted_nums.push_back(nums[j] * nums[j]);
                j++;
            } else if (j >= nums.size()) {
                sorted_nums.push_back(nums[i] * nums[i]);
                i--;
            } else {
                if (abs(nums[i]) < abs(nums[j])) {
                    sorted_nums.push_back(nums[i] * nums[i]);
                    i--;
                } else {
                    sorted_nums.push_back(nums[j] * nums[j]);
                    j++;
                }
            }
        }

        return sorted_nums;
    }
};