leetcode_112번 - Path Sum(이차수, 깊이 우선 검색, 귀속과 교체 방법)

Path Sum

 
Total Accepted: 50593 Total Submissions: 169742 My Submissions
Question
 Solution 
 
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. For example:
Given the below binary tree and  sum = 22 ,

              5

             / \

            4   8

           /   / \

          11  13  4

         /  \      \

        7    2      1

return true, as there exist a root-to-leaf path  5->4->11->2  which sum is 22.
 
Hide Tags
 
Tree   Depth-first Search
Have you met this question in a real interview? 
Yes
 
No
 
Discuss
이 문제는 주어진 값과 같은 경로가 있는지 찾아내야 한다. 깊이 우선 검색 방법으로 아래로 검색할 때마다 현재 결점까지의 경로를 기록하고 잎 노드에 도착할 때
그와 같은지 아닌지를 판단하고 판단의 결과를 거슬러 올라가면 된다.

#include<iostream>

#include<stack>

#include<set>



using namespace std;

// Definition for binary tree

struct TreeNode

{

	int val;

    TreeNode *left;

	TreeNode *right;

	TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};



bool ifsum(TreeNode* root,int sum,int cursum)

{

	if(root==NULL)

		return false;

	if(root->left==NULL&&root->right==NULL)

		return cursum+root->val==sum;

	

	if(root->left!=NULL||root->right!=NULL)

		return ifsum(root->left,sum,cursum+root->val)||ifsum(root->right,sum,cursum+root->val);

}

bool hasPathSum(TreeNode *root, int sum) {

	return ifsum(root,sum,0);

}

int main()

{



}

기본적으로 위와 유사한 방법이 있다. 단지 현재의 경로를 바깥에 놓아 이주 변수로 삼았을 뿐이다. 여기서 주의해야 할 것은 매번 아래로 검색한 후에 이전에 현재 결점 값을 추가한 것을 기억해야 한다.
 

#include<iostream>

#include<stack>

#include<set>



using namespace std;

// Definition for binary tree

struct TreeNode

{

	int val;

    TreeNode *left;

	TreeNode *right;

	TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};



int sum_temp;

int targetsum;

bool ifsum(TreeNode* root)

{

	if(root==NULL)

		return false;

	if(root->left==NULL&&root->right==NULL)

		return targetsum+root->val==sum_temp;



	targetsum+=root->val;

	bool res1=ifsum(root->left);

	bool res2=ifsum(root->right);



	targetsum-=root->val;// ， ， ， 



	return res1||res2;

}



bool hasPathSum(TreeNode *root, int sum) {

	sum_temp=sum;

	targetsum=0;

	return ifsum(root);

}

int main()

{



}

깊이 우선 수색의 사상은 여기에서 교체된 방법으로 창고를 채택하는 데 쓰인다.깊이 우선 검색을 합니다. 여기서 각 노드에 대해pair 변수를 만듭니다. 하나는 노드이고, 다른 하나는 뿌리 노드에서 다음 노드까지의 길이입니다. 그리고 깊이 우선 검색을 하고 잎 노드가 돌아오면 다른 결점은 한 번에 아래로 가져옵니다.

#include<iostream>

#include<stack>

#include<utility>

//#include<set>

//#include<map>

using namespace std;

// Definition for binary tree

struct TreeNode

{

	int val;

    TreeNode *left;

	TreeNode *right;

	TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};



bool hasPathSum(TreeNode *root, int sum) {

	if(root==NULL)

		return false;

	stack<pair<TreeNode*,int> > sta_temp;

	sta_temp.push(make_pair(root,root->val));

	TreeNode* node_temp;

	int sum_temp;

	while(!sta_temp.empty())

	{

		node_temp=sta_temp.top().first;

		sum_temp=sta_temp.top().second;

		sta_temp.pop();

		if(node_temp->left==NULL&&node_temp->right==NULL)

		{

			if(sum_temp==sum)

				return true;

		}

		if(node_temp->left!=NULL)

		{

			sta_temp.push(make_pair(node_temp->left,node_temp->left->val+sum_temp));

		}

		if(node_temp->right!=NULL)

		{

			sta_temp.push(make_pair(node_temp->right,node_temp->right->val+sum_temp));

		}

	}

	return false;

}

int main()

{



}