IT面接と筆記試験はどう対応しますか?
2851 ワード
112.Path Sumは経路と
二叉の木と数字をあげて、ルートの結点から葉っぱの結点までの経路を探します.パス上の結点のものと、与えられた数字に等しいです.
使用したデータ構造:vector、stack、queue使用の思想:深さ優先遍歴、広さ優先遍歴、再帰
二叉の木と数字をあげて、ルートの結点から葉っぱの結点までの経路を探します.パス上の結点のものと、与えられた数字に等しいです.
使用したデータ構造: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 nodes;
stack 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 nodes;
queue 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;
}
};