리코드의 두 갈래 나무 문제 II
2533 단어 Leetcode
제목 1: Balanced Binary Tree
Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced tree is defined as a binary tree in which the depth of the two subtree of every node never differ by more than 1.
사고방식: 균형 트리를 판단하는 것은 나무의 높이에 대한 판단으로 나무의 높이를 구하는 알고리즘을 개조할 수 있다.한 나무는 균형 두 갈래 나무의 충분한 조건은 좌우자 나무는 균형 두 갈래 나무이고 높이차는 1을 넘지 않는다는 것이다.
class Solution {
public:
vector generateTrees(int low, int high){
vector res;
if(low>high){
res.push_back(NULL); // ！
return res;
}
else{
for(int i=low; i<=high; i++){
vector left=generateTrees(low, i-1);
vector right=generateTrees(i+1, high);
TreeNode *root;
for(int j=0; jleft=left[j];
root->right=right[k];
res.push_back(root);
}
}
}
return res;
}
}
vector generateTrees(int n) {
vector res;
if(n==0){
res.push_back(NULL);
return res;
}
return generateTrees(1, n);
}
}; 제목 2:
Maximum Depth of Binary Tree
Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
사고방식: 수의 높이를 구한다.고전 알고리즘.
class Solution {
public:
int maxDepth(TreeNode *root) {
if(root==NULL) return 0; // leaf node
int left=maxDepth(root->left);
int right=maxDepth(root->right);
return 1+max(left, right);
}
};제목 3: Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
사고방식: 이 문제는 이전 문제와 다르기 때문에leafnode를 찾아야 합니다.
class Solution {
public:
int minDepth(TreeNode *root) {
if(root==NULL) return 0;
if(root->left==NULL && root->right==NULL) return 1; //
int left,right;
left=right=1<<12;
if(root->left)
left=minDepth(root->left);
if(root->right)
right=minDepth(root->right);
return 1+min(left, right);
}
};이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
LeetCode 문제풀이 노트 113.경로 총 II경로 총 II 제목 요구 사항 문제풀이 두 갈래 나무와 목표와 뿌리 노드에서 잎 노드까지의 모든 경로를 찾는 것은 목표와 같은 경로입니다. 설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다. 예: 다음과 같은 두 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
