求二叉树中最大和的路径

实验目的

1. 熟悉 C/C++ 语言的集成开发环境
2. 回顾数据结构中关于二叉树的有关运算
3. 加深对递归过程的理解

---

问题描述

假设二叉树中的所有结点值为 int 类型，利用二叉树存储，设计递归算法求二叉树 bt 中从根结点到叶子结点路径和最大的一条路径

样例输入

输入数据格式为前序遍历，空节点用 # 表示

1 2 6 # # # 5 3 # # 2 # #

样例输出

一行一个整数,为二叉树中最大路径和的数

之后若干行,代表所有有可能存在的最大和路径,从根节点开始,每个节点由空格隔开,一行一条路径

9
1 2 6
1 5 3

---

题解与分析

本题主要的思路是递归求解最大深度,再用最大深度的值进行的深度优先搜索,进而找出所有可能存在的最大和路径

二叉树的输入,建立和初始化

首先是一个经典的二叉树节点结构

typedef struct node
{
    struct node *lchild, *rchild;
    int value;
} Node, *BTree;

我们关注一下题目中给出的输入格式

空节点用 # 表示

则我们需要判断当前输入是否为数字

下述函数使用输入流来判断当前字符流中的数据是否为一个数字,若为数字返回 true ,反之返回 false

bool isNumber(const string &str) //判断字符串是否为数字
{
    istringstream sin(str);
    double test;
    return sin >> test && sin.eof();
}

接下来进入建树环节,由于给出的是前序遍历,则一个个读入节点的值,递归建立树的结构

void createBTree(BTree &T)
{
    string tmp;
    cin >> tmp;
    if (!isNumber(tmp))
        T = NULL;
    else
    {
        T = new Node;
        T->value = atoi(tmp.c_str());
        createBTree(T->lchild);
        createBTree(T->rchild);
    }
}

至此二叉树已经建立完毕,可以进行下一步操作

二叉树的多重路径性

对于二叉树的最大和路径,首先可以确定的是其最大和路径可能存在多条,给出的样例可以得出 1-->2-->6 和 1-->5-->3 的两条路径

故声明一个二维的向量 res 存储可能的多个结果

vector<vector<int>> res;

求二叉树中最大深度

本函数递归调用自身,通过返回值返回二叉树的最大深度,基本思路是碰到值为空(当前这个点不存在)就返回 0 ,在当前节点不为空的情况下接受两个子节点的返回值,向外层递归返回左右两个节点中最大的 value 值与本身的 value 值的总和,为此函数传入根节点即可得到二叉树的最大深度

int maxDeepth(BTree T)
{
    if (!T)
        return 0;
    int maxChild = max(maxDeepth(T->lchild), maxDeepth(T->rchild));
    return maxChild + T->value;
}

利用二叉树的最大深度获取路径

对于已求出的最大深度,采用深度优先搜索的方式，枚举每一条从根节点到叶子节点的路径。当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径,此时将缓存向量插入二维向量中,即完成了一条路径的存储

void maxPath(BTree root, int sum)
{
    if (!root)
        return;
    tmp.push_back(root->value);
    if (root->value == sum && (!root->lchild && !root->rchild))
        res.push_back(tmp);
    maxPath(root->lchild, sum - root->value);
    maxPath(root->rchild, sum - root->value);
    tmp.pop_back();
}

最终代码

基本上是将上面的几个部分整合起来,就可以解出当前的最大深度,再把最大深度丢给深度优先搜索可以得到最大和路径,算法大概的时间复杂度是 $O(n^2)$ ,空间复杂度是 $O(n)$ ,其中 $n$ 是二叉树的节点数

#include <bits/stdc++.h>
#define Ansel_DEBUG
using namespace std;
typedef struct node
{
    struct node *lchild, *rchild;
    int value;
} Node, *BTree;
vector<vector<int>> res;
vector<int> tmp;
bool isNumber(const string &str) //判断字符串是否为数字
{
    istringstream sin(str);
    double test;
    return sin >> test && sin.eof();
}
void createBTree(BTree &T)
{
    string tmp;
    cin >> tmp;
    if (!isNumber(tmp))
        T = NULL;
    else
    {
        T = new Node;
        T->value = atoi(tmp.c_str());
        createBTree(T->lchild);
        createBTree(T->rchild);
    }
}
int maxDeepth(BTree T)
{
    if (!T)
        return 0;
    int maxChild = max(maxDeepth(T->lchild), maxDeepth(T->rchild));
    return maxChild + T->value;
}
void maxPath(BTree root, int sum)
{
    if (!root)
        return;
    tmp.push_back(root->value);
    if (root->value == sum && (!root->lchild && !root->rchild))
        res.push_back(tmp);
    maxPath(root->lchild, sum - root->value);
    maxPath(root->rchild, sum - root->value);
    tmp.pop_back();
}
int main()
{
#ifdef Ansel_DEBUG
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif
    BTree T;
    createBTree(T);
    cout << maxDeepth(T) << endl;
    maxPath(T, maxDeepth(T));
    for_each(res.begin(), res.end(),
             [](vector<int> subres)
             {
                 for (int i = 0; i < subres.size(); i++)
                     cout << subres[i] << " ";
                 cout << endl;
             });
    return 0;
}