기술나눔

자바 알고리즘 day12

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

자바 알고리즘 day12

  • 199 이진 트리의 오른쪽 모습
  • 637개 이진 트리의 레벨 평균
  • 515 각 트리 행에서 최대값 찾기
  • 429 N-ary 트리의 레벨 순서 순회
  • 116 각 노드의 다음 오른쪽 노드 포인터 채우기

199 이진 트리의 오른쪽 모습

이 질문은 여전히 ​​레이어 순차 순회에 관한 것이지만 처리 방식이 약간 다릅니다.
이미지 설명을 추가해주세요
이 질문에 대한 나의 초기 생각은 처음에 이 사진을 기반으로 생각했기 때문에 잘못되었습니다. 각 레이어의 마지막 노드만 확장하면 된다고 생각했는데 그게 전부였습니다. 그러나 실제로는 잘못된 것입니다. 이 아이디어를 따르면 위 그림에 노드 4가 없으면 결과 집합에 노드 5를 전혀 추가할 수 없습니다. 따라서 이 아이디어는 바람직하지 않습니다.

올바른 생각:
위와 같은 상황을 방지하기 위해 왼쪽 부분도 확장할 수 있습니다. 그래서 올바른 취급입니다. 각 레이어와 각 노드를 확장해야 하지만 각 레이어의 마지막 요소만 결과 집합에 추가하면 됩니다.
결과 세트에 추가할 마지막 요소를 작성하는 방법은 무엇입니까?
각 레이어는 크기를 사용하므로 for 루프 중 계산에 주의하고 마지막 루프에서 결과를 수집합니다.

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> que = new ArrayDeque<>();
        if(root==null){
            return result;
        }
        
        que.offerLast(root);
        while(!que.isEmpty()){
            int size = que.size();
            for(int i = 0;i<size;i++){
                TreeNode temp = que.pollFirst();
                if(i==size-1){
                    result.add(temp.val);
                }
                
                if(temp.left!=null){
                    que.offerLast(temp.left);
                }
                if(temp.right!=null){
                    que.offerLast(temp.right);
                }
                


            }
        }

        return result;

    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33

637개 이진 트리의 레벨 평균

각 레이어의 평균값을 찾으세요.아직 게시판 질문이에요

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        Deque<TreeNode> que = new ArrayDeque<>();
        if(root==null){
            return result;
        }

        que.offerLast(root);
        while(!que.isEmpty()){
            int size = que.size();
            double sum = 0;
            double avg = 0;
            for(int i = 0;i<size;i++){
                TreeNode temp = que.pollFirst();
                sum += temp.val;
                if(temp.left!=null){
                    que.offerLast(temp.left);
                }
                if(temp.right!=null){
                    que.offerLast(temp.right);
                }
                
            }
            avg = sum/size;
            result.add(avg);
        }

        return result;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

515 각 트리 행에서 최대값 찾기

이는 또한 템플릿 질문이므로 각 행을 처리할 때 최대값을 유지하세요.
기억해야 할 유일한 것은 int의 최소값이 Integer.MIN_VALUE라는 것입니다.

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> que = new ArrayDeque<>();
        if(root==null){
            return result;
        }

        que.offerLast(root);
        while(!que.isEmpty()){
            int size = que.size();
            int max = Integer.MIN_VALUE;
            for(int i = 0;i<size;i++){
                TreeNode temp = que.pollFirst();
                if(temp.val > max){
                    max = temp.val;
                }
                if(temp.left!=null){
                    que.offerLast(temp.left);
                }
                if(temp.right!=null){
                    que.offerLast(temp.right);
                }
            }
            result.add(max);
        }

        return result;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

429 N-ary 트리의 레벨 순서 순회

방금 확장 방법을 변경했습니다. 왼쪽 및 오른쪽 하위 트리를 확장하는 대신 자식 목록을 스택에 직접 추가했습니다.
배워야 할 방법이 있습니다.
ArrayDeque는 Deque를 구현하고, Deque는 Queue 인터페이스를 상속하고, Queue는 Collection 인터페이스를 상속하므로 addAll 메소드를 갖습니다. addAll의 매개변수와 관련하여 해당 매개변수 유형은 Collection 유형입니다. 즉, Collection 인터페이스를 구현하는 모든 객체를 수신할 수 있습니다. 여기에는 생각할 수 있는 모든 단일 열 구조가 포함됩니다.

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        Deque<Node> que = new ArrayDeque<>();
        if(root == null){
            return result;
        }

        que.offerLast(root);
        while(!que.isEmpty()){
            int size = que.size();
            List<Integer> curList = new ArrayList<>();
            while(size>0){
                Node temp = que.pollFirst();
                curList.add(temp.val);
                //就是扩展方式变了，变为直接把子节点全部加入到队列中，这也等价于将里面的每个元素从尾部依次加入队列当中。
                que.addAll(temp.children);
                size--;
            }
            result.add(curList);
        }

        return result;
        
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45

116은 각 노드의 다음 오른쪽 노드 포인터를 채웁니다.

아이디어: 레이어 순차 순회와의 차이점은 각 레이어를 처리할 때 변경 사항이 있다는 것입니다. 각 레이어에 도달하면 첫 번째 노드를 별도로 꺼내야 합니다. 물론 꺼낸 후 먼저 확장해야 합니다. 아직 다음 레이어가 남아 있기 때문입니다. 그런 다음 레이어의 나머지 노드 탐색을 시작합니다. 순회는 주로 현재 que의 크기에 따라 구현됩니다. 이 레이어의 첫 번째 노드가 제거되었으므로 순회 중에 i는 =1부터 시작됩니다. 각 노드를 처리하는 동안 수행해야 할 작업은 포인팅을 수정하는 것입니다. 즉, 첫 번째 노드의 다음 노드는 나중에 스택에서 팝된 두 번째 노드를 가리키고, cur은 다음 노드로 이동합니다. 그리고 이 과정에서 왼쪽 및 오른쪽 하위 노드를 확장하는 것을 잊지 마세요.

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        Deque<Node> que = new ArrayDeque<>();
        if(root==null){
            return root;
        }

        que.offerLast(root);
        while(!que.isEmpty()){
            //每层先取出第一个节点
            int size = que.size();
            Node cur = que.pollFirst();
            //扩展它
            if(cur.left!=null){
                que.offerLast(cur.left);
            }
            if(cur.right!=null){
                que.offerLast(cur.right);
            }
            for(int i = 1;i<size;i++){
                Node next = que.pollFirst();
                if(next.left!=null){
                    que.offerLast(next.left);
                }
                if(next.right!=null){
                    que.offerLast(next.right);
                }
                cur.next = next;
                cur = next;
            }
            

        }
        return root;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59

개인 프로필

그는 30년 이상 기술 연구에 전념해 왔으며, java, linux, javascript, php, css 등 다양한 언어에 능숙하며, 오픈 소스 분야에 많은 공헌을 했습니다. 나중에 참조할 수 있도록 기술 개발의 일부 문제를 공유하는 개발자 문서 스테이션입니다.

내 연락처 정보

우편