이 진 트 리 균형 검사

【 성명: 판권 소유, 전재 출처 표시, 상업 용도 로 사용 하지 마 십시오. 연락처:[email protected]] 제목 링크:http://www.nowcoder.com/practice/b6bbed48cd864cf09a34a6ca14a3976f?rp=1&ru=/ta/cracking- the - coding - interview & qru = / ta / cracking - the - coding - interview / question - ranking 제목 설명 은 하나의 함 수 를 실현 하고 이 진 트 리 의 균형 여 부 를 검사 합 니 다. 균형 적 인 정 의 는 다음 과 같 습 니 다. 트 리 의 임의의 노드 에 대해그 두 자목 의 높이 차 는 1 을 초과 하지 않 는 다.트 리 의 끝 점 을 가리 키 는 포인터 TreeNode * root 를 지정 합 니 다. 이 나무의 균형 여 부 를 나타 내 는 bool 을 되 돌려 주 십시오.사고방식 의 가장 간단 한 방법 은 모든 노드 가 재 귀적 으로 그 깊이 를 파악 한 다음 에 비교 하 는 것 이다. 그러나 이렇게 하면 대량의 무의미 한 조작 을 가 져 올 것 이다. 효율 이 높 지 않 으 면 우 리 는 뿌리 노드 에서 잎 결점 까지 검색 하고 거 슬러 올 라 가 는 과정 에서 그 깊이 를 되 돌려 주 며 같은 층 으로 비교 할 수 있다. 만족 하지 않 는 상황 이 있 으 면 바로 끝난다

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

class Balance
{
	public:
		bool isBalance(TreeNode *root)
		{
			// write code here
			if(root==nullptr)
				return true;
			return checkHeight(root)>=0;
		}
		int checkHeight(TreeNode *root)
		{
			if(root==nullptr)
				return 0;
			int leftHeight = checkHeight(root->left);
			if(leftHeight==-1)
				return -1;
			int rightHeight = checkHeight(root->right);
			if(rightHeight==-1)
				return -1;
			if(abs(leftHeight-rightHeight)>1)
				return -1;
			return max(leftHeight,rightHeight)+1;
		}
};

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

프로그래머 면접 금전 - 면접 문제 02.01 - 중복 노드 제거

프로그래머 면접 금전 - 면접 문제 02.01 - 중복 노드 제거 이 문 제 는 두 개의 지침 문제 로 지침 이 움 직 이지 않 고 이동 하려 면 노드 의 지침 을 제거 해 야 합 니 다. 두 가지 관건 이 있 습 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

이 진 트 리 균형 검사

좋은 웹페이지 즐겨찾기