[ leetcode ] Increasing Order Search Tree

 

2021년도 되었겠다 알고리즘 감각을 잃지 않기 위해 오늘부터 하루에 한 문제씩 리트코드 문제를 풀어보려고 합니다. 리트코드에서는 달마다 챌린지? 형태로 하루에 한 문제씩 문제를 공개하는데 한 개씩 해결하는 재미도 있고 영어 공부도 될겸 리트코드를 이용해보려고 합니다...!

 

(취준 끝나고 코딩테스트 준비를 안했더니 다 까먹었네요,,,,흑흑)

 

 

해결한 문제

leetcode.com/problems/increasing-order-search-tree/

Increasing Order Search Tree - LeetCode

 

문제 풀이

 

트리를 이용한 간단한 문제입니다.

트리의 순회 방법 중 중위 순회(inorder) 방식에 대해서 알면 손쉽게 해결할 수 있습니다.

중위 순회 방식으로 문제를 해결하되 해당 노드의 숫자를 단순히 print 하는 것이 아니라 새로운 tree를 구성해야하기 때문에 저는 전역변수로 새로 구성할 tree의 루트 노드를 생성해두고, 순회하면서 구한 노드값들을 추가하는 방식으로 알고리즘을 구현했습니다.

 

단!

전역변수를 사용할 경우 매 메소드가 끝날 때마다 해당 전역변수를 초기화해주는 작업을 해야합니다!!!!

 

 

코드

 

/**
 * 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 {
    static TreeNode answer = null;
    static TreeNode cur = null;
    
    public void inorder(TreeNode root){
        if(root == null){
            return;
        }
        
        inorder(root.left);
        if(answer == null){
            answer = new TreeNode(root.val);
            cur = answer;
        }else{
            cur.right = new TreeNode(root.val);
            cur = cur.right;
        }
        
        inorder(root.right);
    }
    
    public TreeNode increasingBST(TreeNode root) {
        inorder(root);
        TreeNode fi = answer;
        
        answer = null;
        cur = null;
        
        return fi;
    }
}