112. Path Sum 尋找路徑和

給一個二叉樹和一個數(shù)字露泊，尋找一個從根結(jié)點到葉子結(jié)點的路徑瘾婿，使得路徑上結(jié)點的和等于給定的數(shù)字

使用到的數(shù)據(jù)結(jié)構(gòu)：vector、stack膀藐、queue
使用到的思想：深度優(yōu)先遍歷睦焕，廣度優(yōu)先遍歷，遞歸

//深度優(yōu)先遞歸遍歷
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root == NULL)
        {
            return false;
        }
        else if(root->left == NULL && root->right == NULL)
        {
            return sum==root->val;
        }
        else
        {
            return hasPathSum(root->left,sum-root->val) ||
                hasPathSum(root->right,sum-root->val);
        }
    }
};

//非遞歸 棧
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root == NULL)
            return false;
        stack<TreeNode*> nodes;
        stack<int> values;
        nodes.push(root);
        values.push(root->val);
        while(!nodes.empty())
        {
            TreeNode* node = nodes.top();
            nodes.pop();
            int sumvalue = values.top();
            values.pop();
            if(node->left == NULL && node->right == NULL && sum == sumvalue)
            {
                return true;
            }
            if(node->left != NULL)
            {
                nodes.push(node->left);
                values.push(sumvalue+node->left->val);
            }
            if(node->right != NULL)
            {
                nodes.push(node->right);
                values.push(sumvalue+node->right->val);
            }
            
        }
        return false;
    }
};

//非遞歸护糖，隊列
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root == NULL)
            return false;
        queue<TreeNode*> nodes;
        queue<int> values;
        nodes.push(root);
        values.push(root->val);
        while(!nodes.empty())
        {
            TreeNode* node = nodes.front();
            nodes.pop();
            int sumvalue = values.front();
            values.pop();
            if(node->left == NULL && node->right == NULL && sum == sumvalue)
            {
                return true;
            }
            if(node->left != NULL)
            {
                nodes.push(node->left);
                values.push(sumvalue+node->left->val);
            }
            if(node->right != NULL)
            {
                nodes.push(node->right);
                values.push(sumvalue+node->right->val);
            }
            
        }
        return false;
    }
};

怎樣應(yīng)對IT面試與筆試-（一）
怎樣應(yīng)對IT面試與筆試-（二）
怎樣應(yīng)對IT面試與筆試-（三）
怎樣應(yīng)對IT面試與筆試-（四）
怎樣應(yīng)對IT面試與筆試-（五）
怎樣應(yīng)對IT面試與筆試-（五-1）
怎樣應(yīng)對IT面試與筆試-（六）
怎樣應(yīng)對IT面試與筆試-（七）
怎樣應(yīng)對IT面試與筆試-（八）
怎樣應(yīng)對IT面試與筆試-（九）
怎樣應(yīng)對IT面試與筆試-（十）
怎樣應(yīng)對IT面試與筆試-（十一）
怎樣應(yīng)對IT面試與筆試-（十二）
怎樣應(yīng)對IT面試與筆試-（十三）
怎樣應(yīng)對IT面試與筆試-（十四）
怎樣應(yīng)對IT面試與筆試-（十五）
怎樣應(yīng)對IT面試與筆試-（十六）