leetcode 112. 路径总和

由于是二叉树，可以固然可以使用递归方法来解决，有因为是找到给定长度的路径，也可以使用层序遍历的方法。
方法1：递归方法，解析操作过程，首先是，当根节点为空的时候，固然不存在路径，其次是如果当前结点的值与所需的路径长度相同时，需要其左右孩子指针同时为空，才能保证其是满足条件的路径，这种情况就可以返回true。递归，怎么进行下一步递归呢，调用自身，传入的参数需要考虑，分别是左右孩子的传入以及剩余路径长度的传入。
方法2：迭代方法，进行层序遍历，需要两个队列，一个队列需要保存当前层的结点，一个队列保存还需要当前结点以下的路径长度。当保存当前层结点的结点个数不为0的时候，开始进行比较，返回true的条件就是当前的结点的值与所需要上个结点以下所需要的路径长度相同，并且左右孩子同时为空

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) 
    {
        //使用递归方法
        //当根节点为空 返回false
        if(root == nullptr)
        {
            return false;
        }
        if(root->left == nullptr && root->right == nullptr)
        {
            return targetSum == root->val;
        }
        return hasPathSum(root->left,targetSum - root->val) 
                            || hasPathSum(root->right,targetSum - root->val);
    }


    //使用迭代算法
    bool hasPathSum(TreeNode* root, int targetSum) 
    {
        //如果结点为空 返回 false
        if(root == nullptr)
        {
            return false;
        }

        //创建两个队列 一个用来保存到当前结点的距离 一个用来保存访问的结点
        //层序遍历的方法
        queue  queNode;
        queue          queVal;
        queNode.push(root);
        queVal.push(targetSum);
        //当保存结点地址的队列不为空的时候
        while(!queNode.empty())
        {
            int length = queNode.size();        //获取此层结点的长度

            //此层结点不为空的时候进行判断
            while(length--)
            {
                //获取队首结点,并且弹出当前的结点
                TreeNode * node = queNode.front();
                queNode.pop();
                //当 当前结点的值刚好为所需要的值的时候进行此结点左右子树的比较
                if (node->val == queVal.front())
                {
                    //如果左右子树为空
                    //那么证明已经找到
                    if(node->left == nullptr && node->right == nullptr)
                    {
                        return true;
                    }
                }
                //当前结点的值不是所需要的值时，进行下一个结点的访问
                if(node->left != nullptr)
                {
                    queNode.push(node->left);       //压入结点
                    queVal.push(queVal.front() -node->val);         //压入新值
                }
                if(node->right != nullptr)
                {
                    queNode.push(node->right);
                    queVal.push(queVal.front() -node->val);
                }
                //弹出旧值
                queVal.pop();
            }
        }
        return false;
    }

};