[leetcode] 이 진 트 리 의 최대 곱 하기 (나무의 옮 겨 다 니 기)
답 이 많 을 수 있 으 니 결 과 를 10 ^ 9 + 7 로 모드 를 취하 고 돌아 오 세 요.
예시 1:
입력: root = [1, 2, 3, 4, 5, 6] 출력: 110 해석: 빨간색 의 가장 자 리 를 삭제 하고 두 그루 의 나 무 를 얻 습 니 다. 각각 11 과 10 입 니 다.그것들의 곱셈 은 110 (11 * 10) 예시 2 이다.
입력: root = [1, null, 2, 3, 4, null, null, 5, 6] 출력: 90 설명: 빨간색 의 가장 자 리 를 제거 하고 두 그루 의 나 무 를 얻 습 니 다. 각각 15 와 6 입 니 다.그것들의 곱셈 은 90 (15 * 6) 예시 3:
입력: root = [2, 3, 9, 10, 7, 8, 6, 5, 4, 11, 1] 출력: 1025 예시 4:
입력: root = [1, 1] 출력: 1
알림:
나무 마다 최대 50000 개의 노드 가 있 고 적어도 2 개의 노드 가 있다.각 노드 의 값 은 [1, 10000] 사이 입 니 다.
링크:https://leetcode-cn.com/problems/maximum-product-of-splitted-binary-tree
사고 분석:
이 문제 의 주 된 점 은 바로 나무의 편력 이다.방법 은 모든 노드 를 옮 겨 다 니 는 것 입 니 다. ans 는 현재 트 리 의 합계 * 나머지 노드 의 합 계 를 위해 최대 치 를 가 져 옵 니 다.사실은먼저 차례 는 O (n ^ 2) 의 시간 복잡 도 이 고, 차례 는 O (n) 입 니 다.그냥 오 랜 만 에 나 무 를 만 나 서 글 씨 를 잘 못 써 요. 사실 어렵 지 않 은 것 같 아 요. 아니면... 쉬 워 요.아이고.
/**
* 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:
const int MOD = 1e9+7;
long long sum = 0;
long long ans = 0;
long long getCount(TreeNode* rt) //
{
if(!rt) return 0;
return rt->val + getCount(rt->left) + getCount(rt->right);
}
long long dfs(TreeNode* rt) //
{
if(!rt) return 0;
long long tmp = rt->val + dfs(rt->left) + dfs(rt->right);
ans = max(tmp*(sum-tmp), ans);
return tmp;
}
int maxProduct(TreeNode* root) {
sum = getCount(root);
dfs(root);
return ans%MOD;
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
