💛 오늘의 학습 키워드

[DFS/BFS] Increasing Order Search Tree

📝 문제

문제 설명

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.

제한 조건

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

입출력 예

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]

💬 내 풀이

/**
 * 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 head;
    TreeNode ;
    
    public TreeNode increasingBST(TreeNode root) {
        traverse(root);
        return head;
    }
    
    private void traverse(TreeNode node) {
        if (node == null) { return; }

        traverse(node.left);
        TreeNode n = new TreeNode(node.val);
        if (head == null) {
            head = n;
            p = n;
        } else {
            p.right = n;
            p = p.right;
        }
        traverse(node.right);
    }
}

💻 내 접근 방법

1. 가장 left 노드가 root가 되고, 모든 노드가 root의 right 노드가 되도록 다시 배열하는 문제다.
2. 먼저 가장 left 노드를 탐색하고, head가 없으면 현재 노드를 root로 대입한다.
3. head가 존재한다면, right 노드로 추가한다.
4. right 노드를 탐색하면서 반복하도록 구현했다.

💦 회고

Stack으로도 풀고 싶다.