习题6.8 递归求LCA到两点路径

思路：借助后序遍历的思想求解，链式存储递归求解。注意前缀权值在LCA点处扣的次数，如果归在一条路径上要扣一次，否则扣两次。

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

struct BiTree {
    int id;
    BiTree *lson, *rson;
    BiTree ():lson(NULL),rson(NULL), id(0){}
    BiTree (int x):lson(NULL),rson(NULL), id(x){}
    ~BiTree() {
        cout << id << endl;
    }
};

//在二叉树T找A、B（Aid、Bid）结点，Ayes、Byes表示当前是否找到对应的点 length表示根结点到目前的路径长度  
int dfs(BiTree* T, bool& Ayes, bool& Byes, int Aid, int Bid, int length) {
    if (T==NULL || Ayes && Byes) 
        return 0;
    //找到A结点
    if (T->id == Aid) {
        Ayes = true;
        //B结点还未找到
        if (!Byes) {
            int l = dfs(T->lson, Ayes, Byes, Aid, Bid, length+1);
            int r = dfs(T->rson, Ayes, Byes, Aid, Bid, length+1);
            if (Byes) return l+r-length; //B点为A点后代
        }
        return length;
    }
    //找到B结点
    if (T->id == Bid) {
        Byes = true;
        //A结点还未找到
        if (!Ayes) {
            int l = dfs(T->lson, Ayes, Byes, Aid, Bid, length+1);
            int r = dfs(T->rson, Ayes, Byes, Aid, Bid, length+1);
            if (Ayes) return l+r-length; //A点为B点后代
        }
        return length;
    }
    bool flag1 = Ayes|Byes; //true表示：当前点可能是最近公共交点
    int l = dfs(T->lson, Ayes, Byes, Aid, Bid, length+1);
    bool flag2 = Ayes^Byes; //左子树找到一个点
    int r = dfs(T->rson, Ayes, Byes, Aid, Bid, length+1);
    bool flag3 = Ayes&Byes; //右子树也找到一个点
    //A、B都找到了，考虑当前点是否要减去多余的前缀
    if (flag3)
        return l+r-(!flag1 && flag2 ? 2*length : 0); //如果当前结点是公共交点要减去公共前缀
    return l+r; //将权值传给公共交点
}

void _free(BiTree* cur) {
    if (cur == NULL) return ;
    _free(cur->lson);
    _free(cur->rson);
    delete cur;
}

int main() {
    BiTree* T;
    T = new BiTree(1);
    BiTree* cur = T;
    cur->lson = new BiTree(2);
    cur = cur->lson;
    cur->lson = new BiTree(4);
    cur->rson = new BiTree(5);
    cur = cur->rson;
    cur->lson = new BiTree(7);
    cur = cur->lson;
    cur->rson = new BiTree(8);
    cur = T;
    cur->rson = new BiTree(3);
    cur = cur->rson;
    cur->rson = new BiTree(6);
    cur = cur->rson;
    cur->lson = new BiTree(9);
    cur->rson = new BiTree(10);
    // bool flagA = false, flagB = false;
    // cout << dfs(T, flagA, flagB, 4, 5, 0) << endl;
    for (int i = 1; i < 10; i++)
        for (int j = i+1; j <= 10; j++) {
            bool flagA = false, flagB = false;
            cout << i << "-->" << j << " : ";
            cout << dfs(T, flagA, flagB, i, j, 0) << endl;
        }
    cout << endl;
    _free(T);
    return 0;
}