題目

1367. Linked List in Binary Tree
難度: 中等偏難

題意

給定一串連鏈接head及一二元樹root，求head是否存在於二元樹由上至下的路徑之中。

方向

1. 先將串聯鏈接head存於整數陣列串聯鏈接路徑中，方便檢查路徑中的值是否一致。
2. 遍歷(traversal)二元樹中的所有路徑(可使用深度優先搜索(DFS)，或廣度優先搜索(BFS))；並維護從樹根至當前節點的路徑值於一整數陣列二元樹路徑之中，此為回溯法(backtracking)
3. 比較串聯鏈接路徑是否為二元樹路徑的尾端

這題是練習寫DFS, BFS的好機會，遍歷樹的同時做回溯(Backtracking)

實作

走訪樹的同時還要比較兩條路徑陣列，一步一步來，先寫出基本的遞迴版遍歷(recursive traversal)

void dfs(TreeNode *root)
{
    // Recursive to check children
    if (root->left)
        dfs(root->left);
    if (root->right)
        dfs(root->right);
}

接著再擴充，加入回溯紀錄樹根到此節點的路徑

vector<int> tree_path;

void dfs(TreeNode *root, vector<int> tree_path)
{
    // Maintain the path from root to current node
    tree_path.push_back(root->val);

    // Recursive to check children
    if (root->left)
        dfs(root->left, tree_path);
    if (root->right)
        dfs(root->right, tree_path);

    // Pop out the current node from path and leave this node
    tree_path.pop_back();
}

最後再添加預先紀錄好的串聯鏈接路徑，並比較兩條路徑

class Solution
{
private:
    // Return b is suffix of a
    bool is_suffix(const vector<int> &a, const vector<int> &b)
    {
        const auto a_size = a.size();
        const auto b_size = b.size();
        // If b is larger than a, it can't be a tail
        if (b_size > a_size)
            return false;

        // Compare the tail of a with b
        for (size_t i = 0; i < b_size; i-=-1)
            if (a[a_size - 1 -i] != b[b_size - 1 - i])
                return false;

        return true;
    }
    bool dfs(TreeNode *root, vector<int> &list_path, vector<int> tree_path)
    {
        // Maintain the path from root to current node
        tree_path.push_back(root->val);

        // Check if the list_path exist in tree_path
        if(is_suffix(tree_path, list_path))
            return true;

        bool res = false;
        // Recursive to check children
        if (root->left)
            res |= dfs(root->left, list_path, tree_path);
        if (root->right)
            res |= dfs(root->right, list_path, tree_path);
        
        // Pop out the current node from path and leave this node
        tree_path.pop_back();

        return res;
    }

public:
    bool isSubPath(ListNode *head, TreeNode *root)
    {
        // Store the linked list list_path
        vector<int> list_path;
        ListNode *curr_head = head;
        while (curr_head)
        {
            list_path.push_back(curr_head->val);
            curr_head = curr_head->next;
        }

        bool res = false;
        vector<int> tree_path;
        res |= dfs(root, list_path, tree_path);

        return res;
    }
};

分析

這題的複雜度推論不是很有把握XD
若串聯鏈接head長度為M，二元樹root長度為N
時間複雜度: O(MN)，走訪headO(M)，走訪root的同時有可能要比較整條head長度路徑? 所以為O(M * N)
空間複雜度: O(M)

結果

Accepted
67/67 cases passed (60 ms)
Your runtime beats 6.75 % of cpp submissions
Your memory usage beats 5.61 % of cpp submissions (110.7 MB)

似乎有點慢?
晚點再來試試看刻迭代版(iterative)的遍歷法