99클럽 코테 스터디 18일차 TIL | 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.

📝 풀이

class Solution {
    public TreeNode increasingBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        TreeNode newRoot = new TreeNode(0);
        TreeNode newCurrent = newRoot;
        
        // 중위 순회
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                //왼쪽 노드들 저장
                stack.push(current);
                current = current.left;
            }
            
            current = stack.pop();

            newCurrent.right = new TreeNode(current.val);
            newCurrent = newCurrent.right;
            
            current = current.right;
        }
        
        return newRoot.right;
    }
}

재귀함수가 불편해서 스택으로 푼 문제! 새로운 개념으로 접근하니 즐겁게 풀 수 있었다.
개인적으로 생각하는 포인트는 중위순회를 이해하고 푼다는 것.

👀 고찰

힘들게 정처기를 따고 인생에 도움이 안 되는 줄 알았는데, 이렇게 알고리즘에도 이렇게 나와주니 넘 고맙다. 😂 이제부턴 마음을 고쳐먹고 배움을 낭비라 생각하지 않고 열심히 또 공부해야지.