lintcode - 밸런스 트리 - 93

1270 단어
두 갈래 나무를 정해 고도의 균형을 맞추도록 해라.이 문제에 대해 고도가 균형 잡힌 두 갈래 나무의 정의는 두 갈래 나무의 각 노드의 두 개의 하위 나무의 깊이 차이가 1을 넘지 않는다는 것이다. 
예제
두 갈래 나무 주세요 A={3,9,20,#,#,15,7} , B= {3,#,20,15,7} 
A)  3            B)    3 
   / \                  \
  9  20                 20
    /  \                / \
   15   7              15  7

두 갈래 나무 A는 높이 균형이 잡힌 두 갈래 나무지만 B는 아니다
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
   
    int backtracing(TreeNode *root){
        if(!root)
            return 0;
        if(!root->left&&!root->right)
            return 1;
        int L,R;
        if((L=backtracing(root->left))==-1)
            return -1;
        if((R=backtracing(root->right))==-1)
            return -1;
        if(abs(L-R)>1)
            return -1;
        return L>R?L+1:R+1;    
    }   
    bool isBalanced(TreeNode *root) {
        if(!root)
            return true;
        return backtracing(root)!=-1;
    }
};
검지 Offer: 두 갈래 트리 대칭복사(솔)
디자인 모드 어댑터 em C#

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage