[Algo] 二叉树常见题目2

1. 最近公共祖先LCA

BinaryTreeNode *LCA(BinaryTreeNode *root, BinaryTreeNode *a, BinaryTreeNode *b)
{
    if (root == nullptr || root == a || root == b) return root;
    BinaryTreeNode *l = LCA(root->left, a, b), *r = LCA(root->right, a, b);
    if (l == nullptr && r == nullptr) return nullptr;
    if (l != nullptr && r != nullptr) return root;
    return l == nullptr ? r : l;
}

2. 累加和为aim的所有路径

vector<vector<int>> path_list; //最终结果
vector<int> cur_path;
int cur_sum;
// 2. 累加和为aim的所有路径
void sumPath(BinaryTreeNode *root, int aim)
{
    if (root == nullptr) return;
    if (root->left == nullptr && root->right == nullptr)
    {
        // 当前节点是叶节点
        if (cur_sum + root->val == aim)
        {
            cur_path.push_back(root->val);
            path_list.push_back(cur_path);
            cur_path.pop_back();
        }
    }
    else
    {
        // 非叶节点
        cur_sum += root->val;
        cur_path.push_back(root->val);
        sumPath(root->left, aim);
        sumPath(root->right, aim);
        cur_sum -= root->val;
        cur_path.pop_back();
    }
}

3. 判断平衡二叉树

struct retStruct1
{
    int h; // 树的高度
    bool flag; // 是否是平衡二叉树
};
retStruct1 process1(BinaryTreeNode *root)
{
    if (root == nullptr) return retStruct1{0, true};
    retStruct1 ret_l = process1(root->left);
    retStruct1 ret_r = process1(root->right);
    retStruct1 ret;
    ret.flag = ret_l.flag && ret_r.flag && abs(ret_l.h - ret_r.h) <= 1;
    ret.h = max(ret_l.h, ret_r.h) + 1;
    return ret;
}
// 3. 判断平衡二叉树
bool isBBT(BinaryTreeNode *root)
{
    return process1(root).flag;
}

4. 判断搜索二叉树

struct retStruct2
{
    long long max; // 最大值
    long long min; // 最小值
    bool flag; // 是否是搜索二叉树
};
retStruct2 process2(BinaryTreeNode *root)
{
    if (root == nullptr) return retStruct2{INT64_MIN, INT64_MAX, true};
    retStruct2 ret_l = process2(root->left);
    retStruct2 ret_r = process2(root->right);
    retStruct2 ret;
    ret.max = max(max(ret_l.max, ret_r.max), (long long)root->val);
    ret.min = min(min(ret_l.min, ret_r.min), (long long)root->val);
    ret.flag = ret_l.flag && ret_r.flag && ret_l.max < root->val && ret_r.min > root->val;
    return ret;
}
// 4. 判断搜索二叉树
bool isBST(BinaryTreeNode *root)
{
    return process2(root).flag;
}

5. 打家劫舍

struct retStruct3
{
    int withMax; // 包含当前节点的最大值
    int withoutMax; // 不包含当前节点的最大值
};
retStruct3 process3(BinaryTreeNode *root)
{
    if (root == nullptr) return retStruct3{0, 0};
    retStruct3 ret_l = process3(root->left);
    retStruct3 ret_r = process3(root->right);
    return retStruct3{root->val + ret_l.withoutMax + ret_r.withoutMax, max(ret_l.withMax, ret_l.withoutMax) + max(ret_r.withMax, ret_r.withoutMax)};
}
// 5. 打家劫舍
int rob(BinaryTreeNode *root)
{
    retStruct3 result = process3(root);
    return max(result.withMax, result.withoutMax);
}