leetcode 129. 求根到叶子节点数字之和

大耗子 2021年02月18日 19次浏览

题目:129. 求根到叶子节点数字之和

  • 129. 求根到叶子节点数字之和

    给定一个二叉树,它的每个结点都存放一个 0-9 的数字,每条从根到叶子节点的路径都代表一个数字。

    例如,从根到叶子节点路径 1->2->3 代表数字 123

    计算从根到叶子节点生成的所有数字之和。

    说明: 叶子节点是指没有子节点的节点。

    示例 1:

    输入: [1,2,3]
        1
       / \
      2   3
    输出: 25
    解释:
    从根到叶子节点路径 1->2 代表数字 12.
    从根到叶子节点路径 1->3 代表数字 13.
    因此,数字总和 = 12 + 13 = 25.
    

    示例 2:

    输入: [4,9,0,5,1]
        4
       / \
      9   0
     / \
    5   1
    输出: 1026
    解释:
    从根到叶子节点路径 4->9->5 代表数字 495.
    从根到叶子节点路径 4->9->1 代表数字 491.
    从根到叶子节点路径 4->0 代表数字 40.
    因此,数字总和 = 495 + 491 + 40 = 1026.
    

解题思路

使用递归子树,返回叶子结点计算的路径和到子树上,子树返回给根。

相当于叶子结点作为了一个只有一个结点的树而已。

路径使用vector结构作为栈进行存储。

代码


class Solution {
public:
	int sumNumbers(TreeNode* root) {
		if (!root) return 0;
		vector<int> nums; // 这个nums作为一个栈去是使用

		return sumCore(root, nums);
	}

	int sumCore(TreeNode* root, vector<int> &nums) {
		if (!root) return 0;  // 由于没有对左右子树判断,直接返回0省事
		int sum = 0;
        // 将结点数据入栈
		nums.push_back(root->val);
		// 如果没有左右子结点,说明是叶子结点,需要计算路径数据
		if (!root->left && !root->right) {
            // 计算路径数据
			sum = arrToint(nums);
			nums.pop_back();
			return sum;
		}
        // 将左右子树继续递归,直到没有子树,此处没有判断没有子树不递归,再最开始的!root做了判断
        // 将子树计算的和加起来
		sum += sumCore(root->left, nums);
		sum += sumCore(root->right, nums);
        // 一定要记得出栈
		nums.pop_back();
		return sum;
	}
	// 计算栈数据转化为数字
	int arrToint(vector<int> &nums) {
		if (nums.size() == 0) return 0;
		int sum = 0;
		sum = nums[0];
		for (int i = 1; i < nums.size(); i++)
		{	
			sum *= 10;
			sum += nums[i];
		}
		return sum;
	}
};