C++LeetCode 실현(129.잎 노드 숫자 에 뿌리 를 구 하 는 합)

[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.
Note: A leaf is a node with no children.
Example:
Input: [1,2,3]
1
/ \
2   3
Output: 25
Explanation:
The root-to-leaf path
1->2
represents the number
12
.
The root-to-leaf path
1->3
represents the number
13
.
Therefore, sum = 12 + 13 =
25
.
Example 2:
Input: [4,9,0,5,1]
4
/ \
9   0
/ \
5   1
Output: 1026
Explanation:
The root-to-leaf path
4->9->5
represents the number 495.
The root-to-leaf path
4->9->1
represents the number 491.
The root-to-leaf path
4->0
represents the number 40.
Therefore, sum = 495 + 491 + 40 =
1026
.
이 뿌리 부터 잎 노드 까지 의 숫자의 합 을 구 하 는 문 제 는 이전의 것 과 같다.  Path Sum  매우 유사 하 다.모두 DFS 재 귀 를 이용 하여 풀 었 다.이 문 제 는 단순히 각 노드 의 숫자 를 더 하 는 것 이 아니 라 새로운 서브 노드 의 숫자 를 만 날 때마다 부모 노드 의 숫자 를 10 배 확대 한 후에 더 해 야 하기 때문이다.잎 결점 까지 옮 겨 다 니 면 현재 의 누적 결과 sum 을 되 돌려 줍 니 다.그렇지 않 으 면 좌우 자 결점 에 대해 각각 재 귀 함 수 를 호출 하고 두 결 과 를 더 하면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return sumNumbersDFS(root, 0);
    }
    int sumNumbersDFS(TreeNode* root, int sum) {
        if (!root) return 0;
        sum = sum * 10 + root->val;
        if (!root->left && !root->right) return sum;
        return sumNumbersDFS(root->left, sum) + sumNumbersDFS(root->right, sum);
    }
};

우 리 는 또한 교체 적 인 쓰기 방법 을 사용 할 수 있 습 니 다.여 기 는 먼저 순차 적 으로 옮 겨 다 니 는 교체 쓰기 방법 을 사용 합 니 다.스 택 을 사용 하여 옮 겨 다 니 는 것 을 보조 합 니 다.먼저 뿌리 결산 점 을 스 택 에 눌 러 넣 은 다음 에 while 순환 을 한 다음 에 스 택 꼭대기 요 소 를 꺼 냅 니 다.만약 에 잎 결산 점 이 라면 그 값 을 결과 res 에 추가 합 니 다.만약 에 오른쪽 자 결점 이 존재 한다 면 그 결점 값 에 현재 결점 값 의 10 배 를 더 한 다음 에 오른쪽 자 결점 을 창고 에 눌 러 넣 습 니 다.마찬가지 로 왼쪽 자 결점 이 존재 한다 면 그 결점 값 에 현재 결점 값 의 10 배 를 더 하고 왼쪽 자 결점 을 창고 에 넣 으 면 이전 과 같 지 않 습 니까?  Path Sum  매우 유사 합 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        if (!root) return 0;
        int res = 0;
        stack<TreeNode*> st{{root}};
        while (!st.empty()) {
            TreeNode *t = st.top(); st.pop();
            if (!t->left && !t->right) {
                res += t->val;
            }
            if (t->right) {
                t->right->val += t->val * 10;
                st.push(t->right);
            }
            if (t->left) {
                t->left->val += t->val * 10;
                st.push(t->left);
            }
        }
        return res;
    }
};

Github 동기 화 주소:
https://github.com/grandyang/leetcode/issues/129
유사 한 제목:
Path Sum
Binary Tree Maximum Path Sum
참고 자료:
https://leetcode.com/problems/sum-root-to-leaf-numbers/
https://leetcode.com/problems/sum-root-to-leaf-numbers/discuss/41367/Non-recursive-preorder-traverse-Java-solution
https://leetcode.com/problems/sum-root-to-leaf-numbers/discuss/41452/Iterative-C%2B%2B-solution-using-stack-(similar-to-postorder-traversal)
여기 서 C++구현 LeetCode(129.구 근 에서 엽 노드 숫자 합)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 구 근 에서 엽 노드 숫자 와 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많이 지 켜 주세요!