우객망-검지오피스-균형이차수

1384 단어
제목: 두 갈래 나무를 입력하여 이 두 갈래 나무가 균형 두 갈래 나무인지 판단한다.해법1: 사고방식: 상기 문제 두 갈래 나무의 깊이 함수를 이용하여 매번 좌우 노드의 깊이를 비교하면 된다.그러나 이런 방법은 노드를 여러 번 반복하여 시간 효율이 높지 않다.
class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(pRoot == nullptr)
            return true;
        int left = TreeDepth(pRoot->left);
        int right =TreeDepth(pRoot->right);
        int diff = abs(left-right);
        if (diff >1)
            return false;
        return IsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right);
    }
    int TreeDepth(TreeNode* pRoot)
    {
        if(pRoot == nullptr)
            return 0;
        return 1+max(TreeDepth(pRoot->left),TreeDepth(pRoot->right));
    }
};

해법 2: 사고방식: 만약에 자수가 균형 두 갈래 나무가 아니라면 직접 되돌아오는 깊이는 -1이다
class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if (pRoot==nullptr)
            return true;
        return TreeDeep(pRoot)!=-1;
        
    }
    int TreeDeep(TreeNode* pRoot)
    {
        if (pRoot==nullptr)
            return 0;
        int left = TreeDeep(pRoot->left);
        if (left==-1)
            return -1;
        int right =TreeDeep(pRoot->right);
        if (right==-1)
            return -1;
        int diff = abs(left-right);
        return diff>1?-1:max(1+left,1+right);
    }
};
MEVN 스택 서버를 쉽게 설정하는 방법
HTML 요소를 캡처하는 방법

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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