C++에서 나무의 높이 균형을 확인하는 프로그램

<시간/>

이진 트리가 있다고 가정합니다. 높이가 균형을 이루고 있는지 확인해야 합니다. 우리는 높이 균형 트리의 경우 트리의 모든 노드에 대해 왼쪽 하위 트리 높이와 오른쪽 하위 트리 높이의 절대 차이가 0 또는 1이라는 것을 알고 있습니다.

따라서 입력이 다음과 같으면

그러면 출력은 True

가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

dfs() 함수를 정의하면 노드가 필요합니다.
노드가 null이면 -
- 0 반환
l :=1 + dfs(노드 왼쪽)
r :=1 + dfs(노드 오른쪽)
만약 |l - r|> 1, 다음 -
- ret :=거짓
l과 r의 최대값을 반환
주요 방법에서 다음을 수행하십시오 -
ret :=참
dfs(루트)
리턴 렛

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class TreeNode {
   public:
   int val;
   TreeNode *left;
   TreeNode *right;
   TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
   public:
   bool ret;
   int dfs(TreeNode* node){
      if(!node)
         return 0;
      int l = 1 + dfs(node->left);
      int r = 1 + dfs(node->right);
      if(abs(l - r) > 1)
         ret = false;
      return max(l, r);
   }
   bool isBalanced(TreeNode* root) {
      ret = true;
      dfs(root);
      return ret;
   }
};
main(){
   Solution ob;
   TreeNode *root = new TreeNode(25);
   root->left = new TreeNode(19);
   root->right = new TreeNode(4);
   root->left->left = new TreeNode(9);
   root->left->right = new TreeNode(7);
   cout << (ob.isBalanced(root));
}

입력

TreeNode *root = new TreeNode(25);
root->left = new TreeNode(19);
root->right = new TreeNode(4);
root->left->left = new TreeNode(9);
root->left->right = new TreeNode(7);