程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode 129:Sum Root to Leaf Numbers

LeetCode 129:Sum Root to Leaf Numbers

編輯:C++入門知識

LeetCode 129:Sum Root to Leaf Numbers


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.

 

Subscribe to see which companies asked this question

 

class Solution {
public:
	int sumNumbers(TreeNode* root) {
		return dfs(root, 0);
	}

	int dfs(TreeNode* root, int sum){
		if (root == 0) return 0;
		if (root->left == NULL && root->right == NULL)
		{
			return sum * 10 + root->val;
		}

		return dfs(root->left, sum * 10 + root->val) + dfs(root->right, sum * 10 + root->val);
	}
};

\

 

 

#include
#include
#include
using namespace std;

//Definition for binary tree
struct TreeNode
{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution {
public:
	int sumNumbers(TreeNode* root) {
		return dfs(root, 0);
	}

	int dfs(TreeNode* root, int sum){
		if (root == 0) return 0;
		if (root->left == NULL && root->right == NULL)
		{
			return sum * 10 + root->val;
		}

		return dfs(root->left, sum * 10 + root->val) + dfs(root->right, sum * 10 + root->val);
	}
};

	void createTree(TreeNode *&root)
	{
		int i;
		cin >> i;
		if (i != 0)
		{
			root = new TreeNode(i);
			if (root == NULL)
				return;
			createTree(root->left);
			createTree(root->right);
		}
	}

int main()
{
	Solution s;
	TreeNode *root;
	createTree(root);
	int path = s.sumNumbers(root);
    cout << path <

\

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved