怎样应对IT面试与笔试-（十三）

112. Path Sum 寻找路径和

给一个二叉树和一个数字，寻找一个从根结点到叶子结点的路径，使得路径上结点的和等于给定的数字

使用到的数据结构：vector、stack、queue
使用到的思想：深度优先遍历，广度优先遍历，递归

//深度优先递归遍历
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;
    }
};

怎样应对IT面试与笔试-（一）
怎样应对IT面试与笔试-（二）
怎样应对IT面试与笔试-（三）
怎样应对IT面试与笔试-（四）
怎样应对IT面试与笔试-（五）
怎样应对IT面试与笔试-（五-1）
怎样应对IT面试与笔试-（六）
怎样应对IT面试与笔试-（七）
怎样应对IT面试与笔试-（八）
怎样应对IT面试与笔试-（九）
怎样应对IT面试与笔试-（十）
怎样应对IT面试与笔试-（十一）
怎样应对IT面试与笔试-（十二）
怎样应对IT面试与笔试-（十三）
怎样应对IT面试与笔试-（十四）
怎样应对IT面试与笔试-（十五）
怎样应对IT面试与笔试-（十六）