题解 | #二叉树中和为某一值的路径(一)#

class Solution {
private:
    bool DFS(TreeNode* root, int sum) {
        bool flag1 = false,flag2 = false;//flag表示此路两分支（左右孩子）是否被占领，一开始都未被占领
        if(!root->left&&!root->right&&sum==0)return true;//如果是叶子结点，且能量耗尽,即可占领
        if(root->left)flag1 = DFS(root->left, sum - root->left->val);//看左子树有没有被占领
        if(root->right)flag2 = DFS(root->right, sum - root->right->val);//看右子树有没有被占领
        return flag1 || flag2;//若有孩子被占领，父结点也必被占领，想象一下物理上必然要通过父结点
    }

  public:
    bool hasPathSum(TreeNode* root, int sum) {
        //把sum理解为能量，到达某点时，要消耗对应的能量。所以题目=>占领某条路用尽所有能量
        if (!root)return false;//如果根结点为空，直接不行。
        sum = sum - root->val;//首先要站在根结点上，消耗对应能量
        return DFS(root, sum);//用相应的能量走剩下的路
    }
};