[LeetCode]112.Path Sum

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

/********************************* * 日期：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; // 2叉树节点 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 // 找到1条从根节点到叶子节点的路径 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; } }; // 创建2叉树 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; // ⑴代表NULL vector<int> num = {5,4,8,11,⑴,13,7,2,1}; TreeNode* root = CreateTreeByLevel(num); cout<<solution.hasPathSum(root,22)<<endl; }