Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
README.md
tree.cpp

README.md

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.

Solution

递归前序遍历树,并记录经过的数值,当到达叶子时,保存值到vector中, 然后求vector的值即可.

static inline bool isLeaf(TreeNode *root)
{
	return root->left == NULL && root->right == NULL;
}
class Solution {
public:
	int sumNumbers(TreeNode *root) {
		if (root == NULL)
			return 0;
		vector<int> numbers;
		getNumbers(numbers, root, 0);
		int sum = 0;
		for_each(numbers.begin(), numbers.end(), [&sum](int value){sum += value;});
		return sum;
	}
private:
	void getNumbers(vector<int> &result, TreeNode *root, int number) {
		if (root == NULL)
			return;
		number *= 10;
		number += root->val;
		if (isLeaf(root)) {
			result.push_back(number);
		} else {
			getNumbers(result, root->left, number);
			getNumbers(result, root->right, number);
		}
	}
};

以上方法的时间空间复杂度都是O(n)。

时间是不可能优化的,关键空间,我们可以不保存值,直接求解。

class Solution {
public:
	int sumNumbers(TreeNode *root) {
		return sumNumbers(root, 0);
	}
private:
	int sumNumbers(TreeNode *root, int sum) {
		if (root == NULL)
			return 0;
		sum = sum * 10 + root->val;
		if (isLeaf(root)) {
			return sum;
		} else {
			return sumNumbers(root->left, sum) + sumNumbers(root->right, sum);
		}
	}
};

此时空间复杂度为O(1).

You can’t perform that action at this time.