[LeetCode] 129. Sum Root to Leaf Numbers

轉自LeetCode

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>

這題是典型的 DFS 題目

首先先看 recursive 的寫法

思路不困難，就是歷遍然後求和

code 如下

	/**
	* Definition for a binary tree node.
	* 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 sumDFS(root, 0);
	}
	int sumDFS(TreeNode *node, int sum) {
	if(!node) {
	return 0;
	}
	sum = sum * 10 + node->val;
	if(!node->left && !node->right) {
	return sum;
	}
	return sumDFS(node->left, sum) + sumDFS(node->right, sum);
	}
	};

view raw sumRootToLeafNum_2.cpp hosted with ❤ by GitHub

接著看 iteration 的寫法

不同的地方是使用一個 stack 來完成歷遍

code 如下

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	int sumNumbers(TreeNode* root) {
	if(!root) {
	return 0;
	}
	stack<pair<TreeNode*, int>> treeStack;
	treeStack.push({root, root->val});
	int ans = 0;
	while(!treeStack.empty()) {
	const TreeNode *node = treeStack.top().first;
	const int sumVal = treeStack.top().second;
	treeStack.pop();
	if(!node->left && !node->right) {
	ans += sumVal;
	continue;
	}
	if(node->right) {
	treeStack.push({node->right, sumVal * 10 + node->right->val});
	}
	if(node->left) {
	treeStack.push({node->left, sumVal * 10 + node->left->val});
	}
	}
	return ans;
	}
	};

view raw sumRootToLeafNum_1.cpp hosted with ❤ by GitHub