면접 문제 55(二): 균형 두 갈래 나무
3312 단어 검지 Offer
class Solution {
public:
int getDepth(TreeNode* root)
{
if(root == nullptr)
return 0;
int leftH = getDepth(root->left);
int rightH = getDepth(root->right);
return max(leftH, rightH) + 1;
}
bool IsBalanced_Solution(TreeNode* pRoot) {
if(pRoot == nullptr)
return true;
int left = getDepth(pRoot->left);
int right = getDepth(pRoot->right);
int dif = left - right;
if(dif > 1 || dif < -1)
return false;
return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
}
};방법2: 후속 스트리밍 방식으로 두 갈래 나무의 모든 노드를 훑어본다. 한 노드를 훑어보기 전에 우리는 그것의 좌우 나무를 훑어보았기 때문에 중복 스트리밍은 존재하지 않는다.
class Solution {
public:
bool isBalanced(TreeNode* root, int& depth)
{
if(root == nullptr)
{
//depth = 0;
return true;
}
int left = 0, right = 0;
if(isBalanced(root->left, left) && isBalanced(root->right, right))
{
int dif = left - right;
if(dif <= 1 && dif >= -1)
{
depth = max(left, right) + 1;
return true;
}
}
return false;
}
bool IsBalanced_Solution(TreeNode* pRoot) {
int depth = 0;
return isBalanced(pRoot, depth);
}
};이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[검지 Offer] 두 갈래 트리 재구성(전순 시퀀스와 중간 시퀀스, 두 갈래 트리 재구성)두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하십시오. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {1,2,4,7...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
