기억하고싶은것들

java.nio.file.Files 클래스는 Java 1.7 버전부터 제공되었다.

Files 클래스는 static 메서드로만 이루어져 있다.

제공되는 대부분의 메서드는 file, directory를 다룬다.

create

Files.createFile(file)

파일을 생성할 때 사용

만약, parent directory가 존재하진 않는다면 Exception이 발생한다

Files.createDirectory(path)

디렉토리를 생성할 때 사용

만약, parent directory가 존재하진 않는다면 Exception이 발생한다

Files.createDirectories(path)

디렉토리를 생성할 때 사용

위의 메서드들과 다르게 parent directory가 존재하지 않아도 동작한다

    public static void main(String[] args) {

        Path file = Paths.get("test.txt");
        Path path = Paths.get("dir");
        Path path2 = Paths.get("dir2/test");

        try {
            System.out.println(Files.createFile(file));
            Files.writeString(file, "ttttt");
            Files.delete(file);

            Path dirTest = Files.createDirectory(path);
            System.out.println(dirTest);
            System.out.println(Files.exists(dirTest));
            Files.delete(dirTest);

            Path dirTest2 = Files.createDirectories(path2);
            System.out.println(dirTest2);

            System.out.println(dirTest);
            System.out.println(Files.exists(dirTest));

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

walk

1.8 이상에서만 사용 가능

path 경로 및 하위 파일 및 디렉토리 탐색하여 Stream으로 반환

    public static void main(String[] args) {
    
        Path walkPath = Paths.get("src");
        try {
            Stream<Path> stream = Files.walk(walkPath);
            stream.filter(Files::isRegularFile).forEach(p -> System.out.println(p));
            
            Files.walk(walkPath).filter(Files::isDirectory)
                .forEach(p -> System.out.println(p));
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

Path 경로를 탐색하며 해당 경로에 존재하는 모든 Path를 반환하여

해당 Stream을 기반으로 Directory, File 등등 특정 정보를 추출할 수 있다

walkFileTree

파일 시스템 트리를 재귀적으로 순회하는 기능

FileVisitor 객체를 인자로 받는다

public class SimpleFileVisitor implements FileVisitor<Path> {

    @Override
    public FileVisitResult preVisitDirectory(Path dir, BasicFileAttributes attrs) throws IOException {
        System.out.println("preVisit - " + dir.toString());
        return FileVisitResult.CONTINUE;
    }

    @Override
    public FileVisitResult visitFile(Path file, BasicFileAttributes attrs) throws IOException {
        System.out.println("visit - " + file.toString());
        return FileVisitResult.CONTINUE;
    }

    @Override
    public FileVisitResult visitFileFailed(Path file, IOException exc) throws IOException {
        System.out.println("visitFail - " + file.toString());
        return FileVisitResult.CONTINUE;
    }

    @Override
    public FileVisitResult postVisitDirectory(Path dir, IOException exc) throws IOException {
        System.out.println("postVisit - " + dir.toString());
        return FileVisitResult.CONTINUE;
    }

}

FileVisitor 메서드의 return 값으로 FileVisitResult를 반환하는데

FileVisitResult Enum의 각각의 값들을 알아보자.

    public static void main(String[] args) {
    
        Path walkPath = Paths.get("src");
        try {
            System.out.println("-- walk file tree --");
            Files.walkFileTree(walkPath, new SimpleFileVisitor());
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

As a reminder, a binary search tree is a tree that satisfies these constraints:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

BST의 root 노드가 주어지고, 이 노드를 Greater Tree로 변환하여라.

BST의 모든 key값은 -> 초기값 + 해당 노드보다 큰 key값을 가진 노드의 합으로 변경된다. 

아래는 BST가 만족하는 제약사항들이다.

• 왼쪽 하위 트리는 해당 노드의 key값보다 작은 노드들로만 구성된다.
• 오른쪽 하위 트리는 해당 노드의 key값보다 큰 노드들로만 구성된다.
• 오른쪽, 왼쪽의 모든 하위 트리는 BST이다. 

DFS를 이용해서 해당 문제의 답을 구해보자.

자기 자신보다 큰 값을 가지고 있는 노드들의 합을 구해야 하므로 가장 큰 값을 가지고 있는 노드부터 자기 자신의 값을 더해가면서 그 합들을 구해가면 된다. 

BST의 특성상 가장 큰 값은 트리의 오른쪽 노드들만 타고 가면 나오고

가장 끝의 도달한 순간 부터는 해당 노드의 value를 total sum과 더해가면서 노드의 value값을 변환하면 된다. 

    private void dfs(TreeNode node) {
        if (node.right != null) {
            dfs (node.right);
        }
        int temp = node.val;
        node.val = sum + temp;
        sum = node.val;

        if (node.left != null) {
            dfs(node.left);
        }
    }

오른쪽 subTree를 모두 순회한 후에 왼쪽 서브 트리를 같은 방식으로 순회하면 된다.

(왼쪽의 subTree의 경우에도 가장 큰 값은 오른쪽 끝에 존재) 

이제 해당 메서드를 호출하는 메서드를 보자.

누적 sum을 나타내는 값은 전역변수로 선언하였다.

    int sum = 0;
    public TreeNode bstToGst1(TreeNode root) {
        
        if (root != null) {
            dfs(root);
        }

        return root;
    }

문제 출처

leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

Given the root of a binary tree, return the sum of values of its deepest leaves.

binary tree의 root 값이 주어진 상황에서, 가장 끝에 있는 잎들의 합을 반환해라.

dfs를 이용해서 답을 구해 보자. 

dfs를 타고 갈 때마다 level의 값을 하나씩 더해주어 해당 노드의 level을 파악하고

해당 level이 maxLevel보다 큰 경우에는 maxLevel값으로 세팅해 주면서 해결해 나갈 수 있을 것으로 보인다. 

    private void dfs(TreeNode node, int level) {

        if (level  > maxLevel) {
            sum = 0;
            maxLevel = level;
        }

        if (level == maxLevel) {
            sum += node.val;
        }

        if (node.right != null) {
            dfs(node.right, level+1);            
        }

        if (node.left != null) {
            dfs(node.left, level+1);
        }
    }

해당 메서드를 호출하는 내역을 보자

sum, maxLevel은 전역 변수를 사용하였다.

    int sum = 0;
    int maxLevel = 0;

    public int deepestLeavesSum(TreeNode root) {
        int level = 0;

        if (root != null) {
            dfs (root, level);
        }

        return sum;    
    }

문제 출처 

leetcode.com/problems/deepest-leaves-sum/

Given a binary tree, return the sum of values of nodes with even-valued grandparent. 

(A grandparent of a node is the parent of its parent, if it exists.)

If there are no nodes with an even-valued grandparent, return 0.

binary tree가 주어지고, 부모의 부모 ( grand parent) (할아버지)의 value가  짝수인 node의 value합을 구해라 

만약, 부모의 부모의 값이 짝수인 노드가 없다면 0을 반환해라

dfs를 이용하여 해답을 구해보자.

dfs메서드를 호출할때, 해당 노드의 부모와 부모의 부모를 파라미터로 전달하면 특정 노드에서 해당 부모의 부모의 value를 조회할 수 있다. 

    private void dfs(TreeNode node, TreeNode parent, TreeNode grandParent) {
        
        if (grandParent != null && grandParent.val % 2 == 0) {
            rst += node.val;
        }

        if (node.left != null) {
            dfs (node.left, node, parent);
        }

        if (node.right != null) {
            dfs (node.right, node, parent);
        }
    }

해당 메서드를 호출하는 내역을 보자

전역 변수를 사용하여 해결하는 방법이다.

    static int rst = 0;
    public int sumEvenGrandparent(TreeNode root) {
        if (root != null) {
            dfs (root, null, null);
        }
        return rst;
    }

만약, 전역 변수를 사용하지 않고 메서드에서 result를 반환하고 싶은 경우에는 아래와 같이 하면 해결 가능하다.

( 위의 방법과 거의 동일하다. 메서드의 반환타입만 추가되고 해당 값을 반환해주면 된다.)

    public int sumEvenGrandparent(TreeNode root) {
        int rst = 0;
        if (root != null) {
            rst = dfs (root, null, null);
        }
        return rst;
    }
    private int dfs(TreeNode node, TreeNode parent, TreeNode grandParent) {
        
        int rst = 0;
        if (grandParent != null && grandParent.val % 2 == 0) {
            rst += node.val;
        }

        if (node.left != null) {
            rst += dfs (node.left, node, parent);
        }

        if (node.right != null) {
            rst += dfs (node.right, node, parent);
        }

        return rst;
    }