7月7日
相当于遍历原树的同时新建一颗形状相同的“和树”。若和树叶子结点的val等于目标sum，则返回成功，否则返回失败。
递归函数的作用是，输入当前原树中的某个节点和“和树”中对应的节点，返回该节点下是否存在满足要求的路径（树根到叶子结点）。
bool check(TreeNode * originalNode,TreeNode* sumNode)
/** * Definition for a binary tree node. * 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;//还要考虑原树根是null的情况。。。 //if(root==NULL && sum==0)return true; TreeNode * sumTreeRoot = new TreeNode(root->val); TreeNode * sumTreeNode = sumTreeRoot;//和树树根 int c = check(root,sumTreeNode,sum); if(c==1)return true; else return false; } bool check(TreeNode * originalNode,TreeNode * sumNode,int sum){ //printf("Original:%d\tSum:%d\n",originalNode->val,sumNode->val); bool checker1 = false;bool checker2=false; if(originalNode->left!=NULL){ TreeNode* newsumNode1 = addLeftSon((originalNode->left)->val+sumNode->val,sumNode); checker1 = check(originalNode->left,newsumNode1,sum); } if(originalNode->right!=NULL){ TreeNode* newsumNode2 = addRightSon((originalNode->right)->val+sumNode->val,sumNode); checker2 = check(originalNode->right,newsumNode2,sum); } if(originalNode->left==NULL&&originalNode->right==NULL&&sumNode->val==sum){ return true;} return checker1 || checker2; } TreeNode * addLeftSon(int val,TreeNode * node){ TreeNode * sonNode = new TreeNode(val); node->left = sonNode; return sonNode; } TreeNode * addRightSon(int val,TreeNode * node){ TreeNode * sonNode = new TreeNode(val); node->right = sonNode; return sonNode; } }; // /* 需要一颗与原二叉树相同的树来存储截止到当前节点的路径和 1.若存在左子节点，和树新增左子节点，和为当前和树节点的sum+left.val； 1.1check(OriginalTreeNode,SumTreeNode); 2.若存在右子节点。。。同上 n.若不存在左子节点和右子节点，比较当前和树的sum与目标和，若相同，返回1；否则返回no； **/
第一次刷题，本觉得题目很简单，但提交了5次才通过，前后更是花了一个半小时。
有以下逻辑考虑不细致的地方，以后尽量避免：
原文：https://www.cnblogs.com/BoysCryToo/p/13260173.html