[LeetCode] 971. Flip Binary Tree To Match Preorder Traversal / JAVA

> 문제설명

leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/

Flip Binary Tree To Match Preorder Traversal - LeetCode

문제내용 요약

주어진 바이너리 트리에서 노드의 왼쪽 하위노드와 오른쪽 하위노드를 바꾸는 것을 flip이라고 한다.

주어진 바이너리 트리를 pre-order 방식으로 탐색했을 때, 주어진 배열 voyage와 같은 순서로 탐색하기 위해 flip해야 하는 노드의 val값을 리스트에 넣어 반환하라.

 

>IDEA

바이너리 트리를 pre-order(DFS)로 탐색하며 voyage와 비교한다.

voyage와 pre-order의 순서가 다른 경우 하위 노드를 flip하며 pre-order 탐색을 진행한다.

탐색이 끝난 후 pre-order로 탐색한 순서와 voyage가 같다면 리스트를 출력한다.

 

>Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int[] travel;
    int travelIdx;
    ArrayList<Integer> answerList = new ArrayList<>();

    boolean flip(TreeNode treeNode){
        if(treeNode.left == null || treeNode.right == null) return false;
        answerList.add(treeNode.val);
        TreeNode tmp = treeNode.left;
        treeNode.left = treeNode.right;
        treeNode.right = tmp;
        return true;
    }

    void preOrder(TreeNode treeNode, int[] voyage){
        travel[travelIdx] = treeNode.val;
        if(travelIdx < voyage.length- 1)travelIdx++;
        else return;
        if(treeNode.left != null){
            if (treeNode.left.val != voyage[travelIdx]) {
                flip(treeNode);
            }
            preOrder(treeNode.left, voyage);
        }
        if(treeNode.right != null){
            if (treeNode.right.val != voyage[travelIdx]) {
                flip(treeNode);
            }
            preOrder(treeNode.right, voyage);
        }
    }

    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        travel = new int[voyage.length];
        travelIdx = 0;
        preOrder(root, voyage);
        if(!Arrays.equals(travel, voyage)) {
            answerList.clear();
            answerList.add(-1);
        }
        return answerList;
    }
}

> Result

 

flip을 없애고 다음과 같이 구현 할 수도 있다.

 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int[] travel;
    int travelIdx;
    ArrayList<Integer> answerList = new ArrayList<>();

    void preOrder(TreeNode treeNode, int[] voyage){
        travel[travelIdx] = treeNode.val;
        if(travelIdx < voyage.length- 1)travelIdx++;
        else return;
        if(treeNode.left != null){
            if (treeNode.left.val != voyage[travelIdx]) {
                answerList.add(treeNode.val);
                if(treeNode.right != null) preOrder(treeNode.right, voyage);
                preOrder(treeNode.left, voyage);
                return;
            }
        }
        if(treeNode.left != null) preOrder(treeNode.left, voyage);
        if(treeNode.right != null) preOrder(treeNode.right, voyage);
    }

    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        travel = new int[voyage.length];
        travelIdx = 0;
        preOrder(root, voyage);
        if(!Arrays.equals(travel, voyage)) {
            answerList.clear();
            answerList.add(-1);
        }
        return answerList;
    }
}

 

> Result

수행 속도가 줄었다.