C++ 線索二叉樹求最近公共祖先（LCA）

問題背景

給定一棵二叉樹（以擴展前序序列 `#` 表示空節點構建），要求將其線索化為雙向鏈表（中序線索化），並實現查找兩節點的最近公共祖先（LCA）。

線索二叉樹構建

template <typename Type>
class ThreadedTree {
    struct Node {
        Type data;
        Node *left, *right;
        bool ltag, rtag; // true=線索, false=孩子
        Node(Type d=Type()) : data(d), left(nullptr), right(nullptr), ltag(false), rtag(false) {}
    };
    Node *root;
    
    // 中序線索化核心遞歸
    void _InThread(Node *&p, Node *&pre) {
        if (!p) return;
        _InThread(p->left, pre);
        if (pre && !pre->right) { pre->right = p; pre->rtag = true; }
        if (p && !p->left) { p->left = pre; p->ltag = true; }
        pre = p;
        _InThread(p->right, pre);
    }
    
    // 構建雙向鏈表（以 root 為頭節點）
    void _BuildDList(Node *p) {
        Node *cur = First(p); // 最左節點
        root = cur;
        while (cur) { cout << cur->data << ' '; cur = cur->right; }
    }
    
    Node* First(Node *p) { // 中序第一個節點
        if (!p) throw Exception();
        while (p->left) p = p->left;
        return p;
    }
};

LCA 查找算法

利用線索化後的中序序列特性，結合棧模擬遞歸：

Node* _GetLCA(Node *t, Type v1, Type v2) {
    stack st;
    if (_Exists(t, v1) && _Exists(t, v2)) st.push(t);
    
    while (true) {
        if (_Exists(t->left, v1) && _Exists(t->left, v2)) {
            t = t->left; st.push(t);
        } else if (_Exists(t->right, v1) && _Exists(t->right, v2)) {
            t = t->right; st.push(t);
        } else {
            if (!st.empty()) { t = st.top(); st.pop(); return t; }
            return nullptr;
        }
    }
}

bool _Exists(Node *t, Type val) { // 判斷子樹是否包含值
    if (!t) return false;
    if (t->data == val) return true;
    return _Exists(t->left, val) || _Exists(t->right, val);
}

關鍵點分析

測試用例

// 擴展前序：ABCD###EF##G##HI##J#K##
// 對應樹結構：
//         A
//       /   \
//      B     H
//     / \   / \
//    C   E I   J
//   /   / \    \
//  D   F   G    K
// LCA(C, D) = C
// LCA(F, G) = E

優化建議

• 預處理深度與父節點，支援 O(log n) LCA（倍增/ Tarjan 離線）
• 線索化後可直接中序遍歷無需遞歸，適合內存受限環境
• 模板化支援任意可比較類型 `Type`