99클럽 코테 스터디 18일차 TIL 깊이/너비 우선 탐색(DFS/BFS)

 

# 오늘의 학습 키워드 

깊이/너비 우선 탐색(DFS/BFS)

 

# 오늘의 문제 

https://leetcode.com/problems/increasing-order-search-tree/description/

Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.

 

Example 1:

 

Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9]

Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

Example 2:

 

Input: root = [5,1,7]

Output: [1,null,5,null,7]

 

Constraints:

• The number of nodes in the given tree will be in the range [1, 100].
• 0 <= Node.val <= 1000

 

# 나의 풀이방식 

/**
 * 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 {
    TreeNode prevNode = new TreeNode(0);
    TreeNode currNode = new TreeNode(0);

    public TreeNode increasingBST(TreeNode root) {
        prevNode = currNode;
        inorder(root);

        return currNode.right;
    }

    private void inorder(TreeNode node){

        if(node == null){ return ;}

        inorder(node.left);

        prevNode.right = node;
        prevNode.left = null;
        prevNode = node;

        inorder(node.right);

    }
}

 

 

# 오늘의 공부 

BFS, DFS ? 

- 둘 다 그래프를 탐색하는 방법이다. 

 

DFS(깊이우선탐색:Depth-First-Search) 란? 

- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식

- 모든 노드를 바문하고자 하는 경우에 이 방법을 선택 

- 깊이우선탐색(DFS)가 너비우선탐색(BFS)보다 좀더 간단

- 검색 속도는 너비우선탐색(BFS)보다 느림

 

BFS(너비우선탐색:Breadth-First Search) 란? 

- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방식

- 주로 두 노드 사이의 최단 경로를 찾고 싶을때 선택

 

# 오늘의 회고 

처음에 문제를 풀때는 list 변수를 하나 선언하고 순서대로 list에 넣은다음 TreeNode로 변환시키려고 했었는데 너무 비효율적인 코드였다.  잊지말자 중위순회..