【题目】

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

              5
             /             4   8
           /   /           11  13  4
         /  \              7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

【分析】

题目要求是从根节点到叶子节点的一条路径。刚开始没看清楚，还以为随意路径。

题目只要求返回true或者false，因此没有必要记录路径。

【代码】

/*********************************
*   日期：2015-01-01
*   作者：SJF0115
*   题目: 112.Path Sum
*   来源：https://oj.leetcode.com/problems/path-sum/
*   结果：AC
*   来源：LeetCode
*   博客：
*   时间复杂度：O(n)
*   空间复杂度：O(logn)
**********************************/
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 二叉树节点
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == NULL){
            return false;
        }//if
        // 找到一条从根节点到叶子节点的路径
        if(root->left == NULL && root->right == NULL){
            return sum == root->val;
        }//if
        // 左子树
        bool left = hasPathSum(root->left,sum - root->val);
        // 右子树
        bool right = hasPathSum(root->right,sum - root->val);
        return left || right;
    }
};
// 创建二叉树
TreeNode* CreateTreeByLevel(vector<int> num){
    int len = num.size();
    if(len == 0){
        return NULL;
    }//if
    queue<TreeNode*> queue;
    int index = 0;
    // 创建根节点
    TreeNode *root = new TreeNode(num[index++]);
    // 入队列
    queue.push(root);
    TreeNode *p = NULL;
    while(!queue.empty() && index < len){
        // 出队列
        p = queue.front();
        queue.pop();
        // 左节点
        if(index < len && num[index] != -1){
            // 如果不空创建一个节点
            TreeNode *leftNode = new TreeNode(num[index]);
            p->left = leftNode;
            queue.push(leftNode);
        }
        index++;
        // 右节点
        if(index < len && num[index] != -1){
            // 如果不空创建一个节点
            TreeNode *rightNode = new TreeNode(num[index]);
            p->right = rightNode;
            queue.push(rightNode);
        }
        index++;
    }//while
    return root;
}

int main() {
    Solution solution;
    // -1代表NULL
    vector<int> num = {5,4,8,11,-1,13,4,7,2,-1,-1,-1,1};
    TreeNode* root = CreateTreeByLevel(num);
    cout<<solution.hasPathSum(root,22)<<endl;
}

[LeetCode]112.Path Sum