[Leetcode 7/100] Increasing Order Search Tree - Easy

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

Increasing Order Search Tree - LeetCode

주어진 이진탐색트리를 왼쪽 노드의 자식은 없고 오른쪽 노드의 자식만 존재하도록 트리를 순서대로 정렬하는 문제입니다.

이진탐색트리의 특징은 모든 노드의 왼쪽 노드의 값은 루트 노드보다 작으며 오른쪽 노드의 값은 루트 노드의 값 보다 큰 것입니다.

이 특징을 이용하여 노드를 순서대로 순회하게 되면 모든 값이 오름차순으로 정렬되는 것을 알 수 있습니다.

풀이

풀이는 DFS를 활용합니다.

public class IncreasingOrderSearchTree {

    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 prev = null, head = null;
        public TreeNode increasingBST(TreeNode root) {

            if(root == null) return null;
            increasingBST(root.left);

            if(prev != null) {
                root.left = null;
                prev.right = root;
            }

            if(head == null) head = root;
            prev = root;
            increasingBST(root.right);
            return head;

        }
    }
}