[Cracking the coding interview] 한 그루의 나무가 균형이 맞는지 판단하기.
Implement a function to check if a tree is balaned. For the purpose of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one.
생각:
각각 왼쪽 나무가 균형이 맞는지 아닌지를 판단하고 왼쪽 나무의 깊이를 되돌린다. 같은 이치로 오른쪽 나무가 균형이 맞는지 판단하고 오른쪽 나무의 깊이를 되돌린다. 만약에 왼쪽 나무의 깊이의 차이가 1을 넘지 않는다면 현재의 나무가 균형이 맞다는 것을 의미한다.
방법은 다음과 같다(구조 트리의 부분은 참고할 수 있다http://blog.csdn.net/lalor/article/details/7613621):
//// ， ， false
bool isBalanced(struct node *root, int *depth)
{
if (root == NULL)
{
*depth = 0;
return true;
}
int left, right;
if (isBalanced2(root->lchild, &left) && isBalanced2(root->rchild, &right))
{
int diff = left - right;
if (diff <=1 || diff >= -1)
{
*depth = 1 + (left > right ? left : right);
return true;
}
}
return false;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
콜백 함수를 Angular 하위 구성 요소에 전달이 예제는 구성 요소에 함수를 전달하는 것과 관련하여 최근에 직면한 문제를 다룰 것입니다. 국가 목록을 제공하는 콤보 상자 또는 테이블 구성 요소. 지금까지 모든 것이 구성 요소 자체에 캡슐화되었으며 백엔드에 대한 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
