538 : Convert BST to Greater Tree ( leetcode / java )

 

* 해결 과정

 

  BST이므로 이진탐색 트리임에 유의합니다. 하지만 이 문제에서 딱히 상관은 없습니다. 주어진 Tree에서 val값들을 변경 해야 합니다. 처음에는 어떤 방식과 흐름인지 이해하지 못했습니다. 단순히 전위순회, 중위순회, 후위순회 3가지 안에 포함되어 있을 것이라고 생각했습니다. 하지만 오른쪽 맨 아래로 이동 후, 부모로 올라오고 다시 왼쪽 노드로 가는 방식이었습니다. 문제가 원하는 순회의 방법으로 적절하게 이동할 수 있는지가 관건입니다.

 

class Solution {
    
    int sum = 0;
    
    public TreeNode convertBST(TreeNode root) {
        if(root!=null) {
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }
}