二叉树-路径求和

问题：求二叉树中是否存在根节点到叶子节点的路径之和等于给定目标和的情况。

示例:
给定如下二叉树，求是否存在目标和 是27的路径。

          10
         / 
        4   2
       /   / 
      11  11  1
     /        
    6    2      1

结果返回 true, 因为存在路径 10->4->11->2的路径和是27。

bool HasPathSum(Node * node, int sum) {
    if (node == NULL) return false;

    if (node->lchild == NULL && node->rchild == NULL) {
        return sum == node->data;
    }

    return HasPathSum(node->lchild, sum - node->data) || 
           HasPathSum(node->rchild, sum - node->data);
}

二叉树-路径求和II

问题：要求找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

示例:
给定如下二叉树，要求出目标和 是27的路径信息。

          10
         / 
        4   2
       /   / 
      11  15  1
     /      / 
    6    2  5   1

那么应该返回:
[
[10,4,11,2],
[10,2,15]
]

注意： 本题需要加上对路径的存储，使用回溯法，需要注意退步操作。

vector<vector<int>> FindPathSum(Node * node, int sum) {
    vector<vector<int>> result;
    vector<int> tmp;
    if (node == NULL) return result;
    FindPath(node, result, tmp, sum);
    for (int i = 0; i < result.size(); i++) {
        cout << "path " << i << ":n[";
        for (int j = 0; j < result[i].size(); ++j) {
            cout << result[i][j] << " ";
        }
        cout << "]" << endl;
    }
    return result;
}

void FindPath(Node * node, vector<vector<int>>& result, vector<int>& tmp, int sum) {
    if (node == NULL) return;
    tmp.push_back(node->data);
    if (node->lchild == NULL && node->rchild == NULL) {
        if (node->data == sum) {
            result.push_back(tmp);
        }
    }
    FindPath(node->lchild, result, tmp, sum - node->data);
    FindPath(node->rchild, result, tmp, sum - node->data);
    tmp.pop_back();
}

最后

以上就是呆萌摩托为你收集整理的数据结构-二叉树-路径求和二叉树-路径求和二叉树-路径求和II的全部内容，希望文章能够帮你解决数据结构-二叉树-路径求和二叉树-路径求和二叉树-路径求和II所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。