>

이 과제를 해결했습니다. 모든 테스트 사례를 통과했지만 솔루션에 만족하지 않습니다. 나는 이것이 훨씬 매끄럽게 이루어질 수 있다고 확신합니다 (즉, 코드가 적습니다)

Swap operation:Given a tree and a integer, K, we have to swap the subtrees of all the nodes who are at depth h, where h ∈ [K, 2K, 3K,...].

You are given a tree of N nodes where nodes are indexed from [1..N] and it is rooted at 1. You have to perform T swap operations on it, and after each swap operation print the inorder traversal of the current state of the tree.

Input Format: First line of input contains N, number of nodes in tree. Then N lines follow. Here each of ith line (1 <= i <= N) contains two integers, a b, where a is the index of left child, and b is the index of right child of ith node. -1 is used to represent null node. Next line contain an integer, T. Then again T lines follows. Each of these line contains an integer K.

내 코드는 다음과 같습니다 :

import java.io.*;
import java.util.*;
public class Solution {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        final int N = s.nextInt();
        int[][] leafs = new int[N][2];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 2; j++) {
                leafs[i][j] = s.nextInt();
            } 
        }
        int[] depths = new int[s.nextInt()];
        for (int i = 0; i < depths.length; i++) {
            depths[i] = s.nextInt();
        }
        TreeNode leftTree = (leafs[0][0] > -1) ? new TreeNode(leafs[0][0]) : null;
        TreeNode rightTree = (leafs[0][1] > -1) ? new TreeNode(leafs[0][1]) : null;
        if (leafs[0][0] > -1) leftTree.mapChildNodes(leftTree, leafs, (leafs[0][0] > -1) ? 1 : 2, 0, N);
        if (leafs[0][1] > -1) rightTree.mapChildNodes(rightTree, leafs, (leafs[0][0] > -1) ? 2 : 1, 0, N);
        TreeNode mainTree = new TreeNode(1, leftTree, rightTree);
        for(int d : depths) {
            mainTree.swap(mainTree, d, 1); 
            mainTree.inorder(mainTree);
            System.out.println(); 
        }        
    }
}
class TreeNode {
    private int data;
    private TreeNode left;
    private TreeNode right;
    TreeNode(int data) {
        this.data = data;
    }
    TreeNode(int data, TreeNode left, TreeNode right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
    private void insertLeft(int data) {
        if (this.left == null) {
            this.left = new TreeNode(data);
        } else {
            this.left.insertLeft(data);
        }
    }
    private void insertRight(int data) {
        if (this.right == null) {
            this.right = new TreeNode(data);
        } else {
            this.right.insertRight(data);
        } 
    }
    public void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        System.out.print(node.toString());
        inorder(node.right);
    }
    public void mapChildNodes(TreeNode node, int[][] leafs, int i, int j, int arraySize) {
        if (arraySize == 0) return;
        if (leafs[i][j] > -1){
            node.insertLeft(leafs[i][j]);
            mapChildNodes(node.left, leafs, leafs[i][j]-1, 0, arraySize-1);
        } 
        if (leafs[i][j+1] > -1){
            node.insertRight(leafs[i][j+1]);
            mapChildNodes(node.right, leafs, leafs[i][j+1]-1, 0, arraySize-1);
        }  
    }
    public void swap(TreeNode node, int targetDepth, int depth) {
        if(node == null) return;
        if(depth % targetDepth == 0) {
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
        } 
        swap(node.left, targetDepth, depth+1);
        swap(node.right, targetDepth, depth+1);
    }
    @Override
    public String toString() {
        return this.data + " "; 
    }
}

  • 답변 # 1

    현재 솔루션

    현재 솔루션에는 아무런 문제가 없습니다. 트리를 작성하고 스와핑을 한 다음 순차 순회를 수행합니다. 각 단계는 간단한 방식으로 구현되며 코드가 많지 않습니다.그러나, 적은 코드로 코드를 작성하도록 요청했기 때문에 코드를 크게 줄이는 두 가지 방법을 보여 드리겠습니다.

    두 번째 나무를 만들 필요가 없습니다

    생각해 보면, 트리에서 leafs 라는 배열을 읽은 후 이미 완전한 트리 구조를 가지고 있습니다. 노드, 왼쪽/오른쪽 자식 등으로 두 번째 트리를 만들 필요가 없습니다. 배열을 트리 표현으로 사용할 수 있습니다. 그러므로 당신의 모든 TreeNode  코드는 불필요합니다.

    스왑 중에 순차 통과를 인쇄 할 수 있습니다

    지금, 당신은 swap() 를 실행  요청 된 노드를 교환하고 inorder() 를 실행하는 기능  교환 된 트리에서 노드를 인쇄하는 기능. 이것들은 당신이해야 할 유일한 두 가지 작업이므로 두 번의 패스를 수행하는 대신 교환하는 동안 순회를 인쇄 할 수 있습니다.

    개정 된 솔루션

    위의 두 가지 변경을 한 후 코드는 다음과 같습니다. 문제는 루트가 노드 1이되기를 원했기 때문에 배열을 1 기반으로 수정했습니다.

    import java.util.Scanner;
    public class Solution {
        public static final int ROOT_NODE = 1;
        public static void main(String[] args) {
            Scanner s = new Scanner(System.in);
            final int N = s.nextInt();
            int[][] tree = new int[N+ROOT_NODE][2];
            for (int i = ROOT_NODE; i < N+ROOT_NODE; i++) {
                for (int j = 0; j < 2; j++) {
                    tree[i][j] = s.nextInt();
                }
            }
            int numDepths = s.nextInt();
            for (int i = 0; i < numDepths; i++) {
                swap(tree, ROOT_NODE, s.nextInt(), 1);
                System.out.println();
            }
        }
        public static void swap(int [][] tree, int node, int targetDepth,
                int depth) {
            if(node == -1) return;
            if(depth % targetDepth == 0) {
                int temp = tree[node][0];
                tree[node][0] = tree[node][1];
                tree[node][1] = temp;
            }
            swap(tree, tree[node][0], targetDepth, depth+1);
            System.out.print(Integer.toString(node) + " ");
            swap(tree, tree[node][1], targetDepth, depth+1);
        }
    }
    
    

  • 이전 python - 신생아 파이 토닉 계산기
  • 다음 c++ - A * 대 양방향 Dijkstra 알고리즘