home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Linked List in Binary Tree ใน C++ : ตรวจสอบ Linked List เป็น Downward Path ใน Tree

ให้ **Binary Tree Root** และ **Linked List Head** ตรวจสอบว่า **Linked List ทั้งหมด** ตรงกับ **Downward Path** ใดๆ ใน Tree (จาก Node ใด Node หนึ่ง ลงมา Child ต่อเนื่อง) หรือไม่

ตัวอย่าง

List: 1 -> 4 -> 2 -> 6
Tree: (มี Path 1-4-2-6 ลงมา)
Output: true

แนวทาง: DFS + Memoization (DP on Tree x List)

State: (listNode, treeNode, flag)

  • flag = true: ยัง **ไม่เริ่ม Match** (หาจุดเริ่มต้น Path)
  • flag = false: **กำลัง Match อยู่** (ต้อง Match ต่อเนื่อง)

Transitions:

  1. ถ้า listNode == null -> Match สำเร็จ -> True
  2. ถ้า treeNode == null -> Match ล้มเหลว -> False
  3. ถ้า flag == false (Matching):
    • ต้อง listNode->val == treeNode->val ถึงจะต่อได้
    • Next: (listNode->next, treeNode->left, false) OR (listNode->next, treeNode->right, false)
  4. ถ้า flag == true (Searching Start):
    • ถ้า listNode->val == treeNode->val -> ลองเริ่ม Match: (listNode->next, left, false) OR (listNode->next, right, false)
    • **และ** ยังคงหาจุดเริ่มต้นอื่นต่อ: (listNode, left, true) OR (listNode, right, true)
  5. Memoize ผลลัพธ์ใน dp[listNode][treeNode][flag]

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

struct ListNode { int val; ListNode *next; ListNode(int x):val(x),next(NULL){} };
struct TreeNode { int val; TreeNode *left, *right; TreeNode(int x):val(x),left(NULL),right(NULL){} };

class Solution {
public:
    // dp[listNode][treeNode][flag] -> bool
    map<ListNode*, map<TreeNode*, map<bool, bool>>> dp;

    bool solve(ListNode* head, TreeNode* root, bool flag = true) {
        if (!head) return true;
        if (!root) return false;

        if (dp.count(head) && dp[head].count(root) && dp[head][root].count(flag))
            return dp[head][root][flag];

        bool ret = false;
        if (head->val == root->val) {
            // Option 1: Start/Continue Match here
            ret = solve(head->next, root->left, false) || solve(head->next, root->right, false);
            if (ret) return dp[head][root][flag] = true;
        }

        if (!flag) return dp[head][root][flag] = false; // Must match continuously, failed

        // Flag true: Keep searching for start in children
        ret = solve(head, root->left, true) || solve(head, root->right, true);
        return dp[head][root][flag] = ret;
    }

    bool isSubPath(ListNode* head, TreeNode* root) {
        return solve(head, root, true);
    }
};

Input / Output

Input:  List [1,4,2,6], Tree [1,4,4,null,2,2,null,1,null,6,8...]
Output: 1 (true)

ความซับซ้อน (Complexity)

  • States: O(L * N * 2) — L=List Length, N=Tree Nodes
  • Time: O(L * N) — แต่ละ State คำนวณ O(1)
  • Space: O(L * N) — Memoization Map

Optimization Note

Map ช้า ใช้ Array/Vector Index แทน Pointer ได้ (Assign ID ให้ Node) จะเร็วกว่ามากครับ