leetcode_129번 - Sum Root to Leaf Numbers(DFS 기반 귀속)

2367 단어 LeetCode

Sum Root to Leaf Numbers

 
Total Accepted: 45133 Total Submissions: 148808 My Submissions
Question
 Solution 
 
Given a binary tree containing digits from  0-9  only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path  1->2->3  which represents the number  123 .
Find the total sum of all root-to-leaf numbers.
For example,
    1

   / \

  2   3


 
The root-to-leaf path  1->2  represents the number  12 .The root-to-leaf path  1->3  represents the number  13 .
Return the sum = 12 + 13 =  25 .
 
Hide Tags
 
Tree   Depth-first Search
Have you met this question in a real interview? 
Yes
 
No
 
Discuss
이 문제는 DFS에 기반한 귀속을 채택한다.
#include<iostream>

using namespace std;

struct TreeNode

{

	int val;

    TreeNode *left;

    TreeNode *right;

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

};

void digui(TreeNode* root,int len,int &result)

{

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

	{

		result=result+len;

		return;

	}

	if(root->left!=NULL)

	{

		digui(root->left,len*10+root->left->val,result);

	}

	if(root->right!=NULL)

	{

		digui(root->right,len*10+root->right->val,result);

	}

	return;

}

int sumNumbers(TreeNode* root){

	int last=0;

	if(root==NULL)

		return 0;

	digui(root,root->val,last);

	return last;

}

int main()

{

	TreeNode* root=new TreeNode(0);

	root->left=new TreeNode(1);

	root->right=new TreeNode(3);

	cout<<sumNumbers(root)<<endl;

}


  

좋은 웹페이지 즐겨찾기