728x90
반응형
Recursive:
maxDepthSum 함수 : 각 depth에 있는 node들의 합을 구하는 함수
maxDepth 함수에서 while 루프를 통해 최대 depth를 구한다.
leaf node의 합을 구하고 싶으므로 , depth-1 을 사용
#include <iostream>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
int maxDepthSum(TreeNode* root, int depth) {
if (root == nullptr) {
return 0;
}
if (depth == 0) {
return root->val;
}
int leftSum = maxDepthSum(root->left, depth - 1);
int rightSum = maxDepthSum(root->right, depth - 1);
return leftSum + rightSum;
}
int maxDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int depth = 0;
while (maxDepthSum(root, depth) != 0) {
depth++;
}
return depth;
}
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
int depth = maxDepth(root);
int sum = maxDepthSum(root, depth - 1);
std::cout << "Depth: " << depth << std::endl;
std::cout << "Sum of nodes at maximum depth: " << sum << std::endl;
return 0;
}
Iterative:
Queue 를 사용하는 것이 Key Point
while 루프에서 sum을 초기화 하므로 마지막 sum은 leaf 노드들의 합이 된다.
#include <iostream>
#include <queue>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
int maxDepthSum(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int depth = 0;
int sum = 0;
std::queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
sum = 0;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
sum += node->val;
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
depth++;
}
return sum;
}
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
int sum = maxDepthSum(root);
std::cout << "Sum of nodes at maximum depth: " << sum << std::endl;
return 0;
}
728x90
반응형
'Data structure' 카테고리의 다른 글
Find the Maximum Depth or Height of a Tree using Level Order Traversal (2) | 2023.10.03 |
---|---|
Find the Maximum Depth or Height of given Binary Tree (0) | 2023.10.03 |
Linked List(Check if Linked List is Palindrome) (0) | 2023.10.03 |
Queues (0) | 2023.10.03 |
Stacks (0) | 2023.10.03 |