매일 한 문제-검지 Offer 55 - I. 두 갈래 나무의 깊이

2066 단어

제목 정보

  • 시간: 2019-07-04
  • 제목 링크: Leetcode
  • tag: 두 갈래 나무 층계 역행 후 역행
  • 난이도: 간단하다
  • 제목 설명: 두 갈래 나무의 뿌리 노드를 입력하여 이 나무의 깊이를 구한다.뿌리 노드에서 잎 노드까지 순서대로 지나가는 노드(뿌리, 잎 노드 포함)는 나무의 경로를 형성하고 가장 긴 경로의 길이는 나무의 깊이이다

  • 예:
    두 갈래 나무를 정해라[3,9,20,null,null,15,7] ,
        3
       / \
      9  20
        /  \
       15   7
    

    최대 깊이 3을 반환합니다.
    주의하다
    1.   <= 10000
    

    문제 풀이 사고방식


    본제의 난점
    트리의 스트리밍 방식은 전체적으로 깊이 우선 검색(DFS), 폭 우선 검색(BFS)으로 나뉜다.
  • 흔히 볼 수 있는 DFS: 선순환, 중순환, 후순환;
  • 일반적인 BFS: 계층 이동(계층 이동)..

  • 나무의 깊이를 구하려면 나무의 모든 노드를 두루 돌아다녀야 한다.
    구체적인 사고방식
    두 갈래 나무의 층차 반복/광도 우선 검색은 종종 대기열을 이용하여 이루어진다.
    한 층을 훑어볼 때마다 계수기 +1, 훑어볼 때까지 나무의 깊이를 얻을 수 있다.
    주의하다

    코드

    class Solution {
        public int maxDepth(TreeNode root) {
            if(root == null){
                return 0;
            }
          //  queue 
            Queue queue = new LinkedList<>();
            queue.add(root);
            int res = 0;
            while(!queue.isEmpty()){
              // :   queue   node ,  queue;
                for(int i = queue.size();i > 0 ; i--){
                    TreeNode t = queue.poll();
                    if(t.left != null){
                        queue.add(t.left);
                    }
                    if(t.right != null){
                        queue.add(t.right);
                    }
                }
                res++;       
            }
            return res;
        }
    }
    

    복잡도 분석:
  • 시간 복잡도 O(N): N은 나무의 노드 수량이며, 나무의 깊이를 계산하려면 모든 노드를 두루 돌아다녀야 한다..
  • 공간 복잡도 O(N): 최악의 경우(트리가 균형을 이룰 때), 대기열queue N/2 노드를 동시에 저장..

  • 기타 우수 답변


    문제 풀이 사고방식
    이 트리의 깊이와 왼쪽 (오른쪽) 하위 트리의 깊이 사이의 관계입니다.분명히 이 나무의 깊이는 왼쪽 나무의 깊이와 오른쪽 나무의 깊이의 최대치 +1과 같다.
    코드
    class Solution {
        public int maxDepth(TreeNode root) {
            if(root == null) return 0;
            return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
        }
    }
    

    좋은 웹페이지 즐겨찾기