二叉树的路径问题

二叉树的路径是指从二叉树的根节点到叶子节点（叶子节点是指没有子节点的节点）的路径。那么怎么求取二叉树的路径呢？方法1、采用递归访问二叉树的方法，访问节点时先将节点加入到一个path变量中，如果该节点是叶子节点，那么path里面存放的就是从根节点到该叶子节点的路径了，访问完了二叉树的所有节点后即可得到所有路径。方法2、二叉树的后序非递归算法中，辅助结构栈中的节点是当前正在访问的节点的祖先，这样也可以得到根节点到叶子节点的路径。
方法1采用递归的方法，代码如下：

vector<string> binaryTreePaths1(TreeNode* root)
{
    vector<string> ans;
    if (root == NULL)  return ans;
    vector<int> path;
    path.push_back(root->val);
    backtracking(ans, path, root);
    return ans;
}

void backtracking(vector<string> &ans, vector<int> &path, TreeNode* root)
{
    if (root->left == NULL && root->right == NULL)
    {
        string tmp;
        for (int i = 0; i < path.size() - 1; ++i)
            tmp += to_string(path[i]) + "->";
        tmp += to_string(path[path.size() - 1]);
        ans.push_back(tmp);
        return;
    }
    if (root->left != NULL)
    {
        path.push_back(root->left->val); //处理节点
        backtracking(ans, path, root->left); //递归调用
        path.pop_back(); //回溯，撤销处理结果
    }
    if (root->right != NULL)
    {
        path.push_back(root->right->val);
        backtracking(ans, path, root->right);
        path.pop_back();
    }
}

方法2采用后序非递归的方法求二叉树的路径代码如下：

vector<string> binaryTreePaths2(TreeNode* root)
{
    vector<string> ans;
    if (root == NULL)  return ans;
    vector<TreeNode*> vt; //当作一个栈来使用，
    TreeNode *pre = NULL, *cur = root;
    while (cur != NULL || vt.size() != 0)
    {
        if (cur != NULL)
        {
            vt.push_back(cur);
            cur = cur->left;
        }
        else //左子树都访问后要先判断右孩子是否已经访问
        {
            cur = vt.back(); //取当前节点
            if (cur->right != NULL && cur->right != pre) //存在右孩子且还没有访问，那么就先去访问右孩子
                cur = cur->right;
            else
            {
                if (cur->left == NULL && cur->right == NULL)
                {
                    string tmp;
                    for (int i = 0; i < vt.size() - 1; ++i)
                        tmp += to_string(vt[i]->val) + "->";
                    tmp += to_string(vt[vt.size() - 1]->val);
                    ans.push_back(tmp);
                }
                vt.pop_back();
                pre = cur;
                cur = NULL;
            }
        }
    }
    return ans;
}

使用回溯法来解决二叉树的路径问题是一个不错的方法
典序例题1————力扣112.路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

求解该题的思路：我们是要判断二叉树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标值。那么我们就可以对二叉树中的路径一一判断路径上所有节点值相加是否等于目标值，如果找到了就直接返回true，后续的路径就不再需要进行判断，否则就一直判断下去，直到最后也没有找到就说明不存在这样的路径，返回false。代码如下：

//1.递归法求解
bool hasPathSum1(TreeNode* root, int sum)
{
    if (root == NULL)  return false; //空树自然返回false
    if (root->left == NULL && root->right == NULL) //遇到叶子节点就判断
        return sum == root->val;
    return hasPathSum1(root->left, sum - root->val) || hasPathSum1(root->right, sum - root->val);
}
//2.回溯法求解
bool hasPathSum2(TreeNode* root, int sum)
{
    if (root == NULL)  return false;
    int curSum = root->val;
    return traversal(root, sum, curSum);
}

bool traversal(TreeNode *root, int sum, int curSum)
{
    if (root->left == NULL && root->right == NULL)
    {
        return curSum == sum;
    }
    bool flag = false;
    if (root->left != NULL) //先去左子树上寻找
    {
        curSum += root->left->val;
        flag = traversal(root->left, sum, curSum); //去左子树上寻找
        curSum -= root->left->val;
    }
    if (!flag) //左子树上没有找到就去右子树上寻找
    {
        if (root->right != NULL)
        {
            curSum += root->right->val;
            flag = traversal(root->right, sum, curSum); //左子树上没有找到就去右子树上寻找
            curSum -= root->right->val;
        }
    }
    return flag;
}
//3.使用一种数据结构来保存之前访问过的节点，因为我们还有要去访问他们的子节点
bool hasPathSum3(TreeNode *root, int sum)
{
    if (root == NULL)  return false;
    queue<TreeNode*>qu;
    queue<int>sumqu;
    qu.push(root);
    sumqu.push(root->val);
    while (!qu.empty())
    {
        TreeNode *cur = qu.front();
        int curSum = sumqu.front();
        qu.pop();
        sumqu.pop();
        if (cur->left == NULL && cur->right == NULL)
        {
            if (curSum == sum)
                return true;
        }
        if (cur->left != NULL)
        {
            qu.push(cur->left);
            sumqu.push(curSum + cur->left->val);
        }
        if (cur->right != NULL)
        {
            qu.push(cur->right);
            sumqu.push(curSum + cur->right->val);
        }
    }
    return false;
}
//4.当然使用一个栈结构也是可以的，因为这里只是使用一个数据结构来保存之前访问过的节点而已
bool hasPathSum4(TreeNode *root, int sum)
{
    if (root == NULL)  return false;
    stack<TreeNode*>qu;
    stack<int>sumqu;
    qu.push(root);
    sumqu.push(root->val);
    while (!qu.empty())
    {
        TreeNode *cur = qu.top();
        int curSum = sumqu.top();
        qu.pop();
        sumqu.pop();
        if (cur->left == NULL && cur->right == NULL)
        {
            if (curSum == sum)
                return true;
        }
        if (cur->left != NULL)
        {
            qu.push(cur->left);
            sumqu.push(curSum + cur->left->val);
        }
        if (cur->right != NULL)
        {
            qu.push(cur->right);
            sumqu.push(curSum + cur->right->val);
        }
    }
    return false;
}

典型例题2————力扣113.路径总和Ⅱ
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

解题思路：题目要求找到所有从根节点到叶子节点路径总和等于给定目标和的路径，那么就只需要求出一条路径对其进行判断即可。代码如下：

vector<vector<int>> pathSum(TreeNode* root, int sum)
{
    vector<vector<int>> ans;
    if (root == NULL)  return ans;
    vector<int> path;
    path.push_back(root->val);
    int curSum = root->val;
    backtracking(ans, path, root, sum, curSum);
    return ans;
}

void backtracking(vector<vector<int>> &ans, vector<int> &path, TreeNode *root, int sum, int curSum)
{
    if (root->left == NULL && root->right == NULL) //终止条件
    {
        if (curSum == sum)
            ans.push_back(path);
        return;
    }
    if (root->left != NULL)
    {
        path.push_back(root->left->val); //处理节点
        curSum += root->left->val;
        backtracking(ans, path, root->left, sum, curSum); //递归
        curSum -= root->left->val; //回溯，撤销处理结果
        path.pop_back();
    }
    if (root->right != NULL)
    {
        path.push_back(root->right->val); //处理节点
        curSum += root->right->val;
        backtracking(ans, path, root->right, sum, curSum); //递归
        curSum -= root->right->val; //回溯，撤销处理结果
        path.pop_back();
    }
}

典型例题3————力扣437路径总和Ⅲ
给定一个二叉树，它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
解题思路：这题不同于前面的各题，这里的路径不一定从根节点出发，也不一定终止于叶子节点，那么我们就只能依次以当前节点为根节点去它的子树上寻找路径和为给定值的路径了，那么对于当前节点来说就有三种处理情况：1.以当前节点为作为头节点的路径数量、2.以当前节点的左孩子节点作为头节点的路径数量、3.以当前节点的右孩子节点作为头节点的路径数量。按照这样的分类，不难想到使用递归处理的方法。代码如下：

int pathSum1(TreeNode* root, int sum)
{
    if (root == nullptr)   return 0;
    int midcount = 0, leftcount = 0, rightcount = 0;
    backtracking(root, sum, midcount); //以当前节点作为头节点的路径数量
    leftcount = pathSum1(root->left, sum); //以当前节点的左孩子节点为头节点的路径数量
    rightcount = pathSum1(root->right, sum); //以当前节点的右孩子节点作为头节点的路径数量
    return midcount + leftcount + rightcount; //返回路径数量总和
}

int pathCount(TreeNode* root, int sum) //递归法计算以root为头节点时满足要求的路径数量
{
    if (root == nullptr)   return 0;
    sum -= root->val;
    int res = (sum == 0 ? 1 : 0);
    return res + pathCount(root->left, sum) + pathCount(root->right, sum);
}
void backtracking(TreeNode* root, int sum, int &count) //回溯法计算以root为头节点时满足要求的路径数量
{
    if (sum == root->val)
        ++count;
    if (root->left != nullptr)
        backtracking(root->left, sum - root->val, count);
    if (root->right != nullptr)
        backtracking(root->right, sum - root->val, count);
}

对于这题，还存在着一种更高效的方法，使用前缀和的思想，前缀和就是指到达当前元素的路径上之前所有元素的和，对于路径上的两个点来说，如果其前缀和是一样的，那么我们就直到这两个节点之间的元素和就为0，所以对于本题来说，如果存在两个节点前缀和相差sum，那么这两个节点之间的元素之和就为sum。代码如下：

int pathSum2(TreeNode* root, int sum)
{
    if (root == nullptr)   return 0;
    unordered_map<int, int>map; //key对应着前缀和，value对应着前缀和出现的次数
    map[0] = 1; //起始条件
    return backtracking(root, map, sum, 0);
}

int backtracking(TreeNode* root, unordered_map<int, int> &map, int sum, int curSum)
{
    curSum += root->val;
    int res = 0; //返回路径数量
    if (map.find(curSum - sum) != map.end()) //存在前缀和相差sum的两个节点
        res += map[curSum - sum];
    ++map[curSum]; //将当前节点的前缀和加上
    if (root->left != nullptr)
        res += backtracking(root->left, map, sum, curSum); //去左子树上找
    if (root->right != nullptr)
        res += backtracking(root->right, map, sum, curSum); //去右子树上找
    --map[curSum]; //减去当前节点的前缀和，保证map中存放的只能是某节点之前节点的前缀和
    return res;
}