LeetCode OJ-129.Sum Root to Leaf Numbers

LeetCode OJ-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 .

제목 이해


뿌리 노드에서 최하층의 잎 노드로 구성된 경로는 하나의 수를 나타낸다. 제목에서 말한 바와 같이 1->2->3은 123을 나타낸다.제목은 두 갈래 나무의 모든 경로가 대표하는 수의 합을 요구합니다. 여기는 간단한 순서대로 처리할 수 있습니다. 문자열에 이 노드가 표시하는 숫자 문자를 추가할 때마다 최하층의 잎 노드를 만나면 문자열을 정형값으로 바꾸어 화합을 구할 수 있습니다.끝 위치는 처음에 추가한 문자를 삭제하고 거슬러 올라가야 합니다.

Code

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

void cal_sum(TreeNode *root, string &nums, int &sum)
{
    if (root == 0) {
        return ;
    }

    nums.push_back('0' + root->val);

    if (root != 0 && root->left == 0 && root->right == 0) {
        sum += stoi(nums);
    }

    cal_sum(root->left, nums, sum);
    cal_sum(root->right, nums, sum);

    nums.pop_back();
    return ;
}

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        int sum = 0;
        string nums;
        cal_sum(root, nums, sum);
        return sum;
    }
};

좋은 웹페이지 즐겨찾기