LeetCode 543. 두 갈래 나무의 지름

.제목: 두 갈래 나무를 정하려면 직경의 길이를 계산해야 한다.두 갈래 나무의 지름 길이는 두 개의 결점 경로 길이 중 최대값입니다.이 경로는 루트 결점을 통과할 수 있습니다..
예: 두 갈래 트리 지정하기
      1
     / \
    2   3
   / \     
  4   5    

3을 되돌려줍니다. 길이는 경로 [4, 2, 1, 3] 또는 [5, 2, 1, 3]입니다.
참고: 두 결점 사이의 경로 길이는 둘 사이의 모서리 수로 표시됩니다.
  • 문제 풀이 사고방식 방법 1, 2갈래 나무의 직경은 각 노드의 좌우 깊이의 합이 가장 크다.전역 변수 max만 사용하여 깊이를 구하는 동시에 각 노드의 좌우 깊이의 합을 기록하는 최대 값을 기록합니다.코드 구현(C++)
  •  int sum = 0;
        int height(TreeNode* root)           // 
        {
            if(!root)
                return 0;
            int a = height(root->left);
            int b = height(root->right);
            sum = max(sum, a + b);
            return a > b? a+1: b+1;
        }
    
        int diameterOfBinaryTree(TreeNode* root) {
            height(root);
            return sum;
        }
    

    방법2: 두 갈래 나무의 직경: 두 갈래 나무 중 한 결점에서 다른 노드로 가는 가장 긴 경로, 두 갈래 나무의 직경은 분리와 귀속의 사상을 채택한다. 뿌리 노드가 루트인 두 갈래 나무의 직경=max(root-left의 직경, root->right의 직경, root->left의 최대 깊이+root->right의 최대 깊이+1)
    코드 구현:
    int sum = 0;
        int height(TreeNode* root)           // 
        {
            if(!root)
                return 0;
            int a = height(root->left);
            int b = height(root->right);
            sum = max(sum, a + b);
            return a > b? a+1: b+1;
        }
    
        int diameterOfBinaryTree(TreeNode* root) {
            if(!root)
                return 0;
            int l = diameterOfBinaryTree(root->left);             // 
            int r = diameterOfBinaryTree(root->right);          // 
            int hl = height(root->left);                       // 
            int hr = height(root->right);                       // 
            return max(max(l,r) ,hl + hr);
        }
    

    좋은 웹페이지 즐겨찾기