Leetcode - 285. Inorder Successor in BST

문제

BST와 한 노드가 주어진다. 해당 노드보다 다음 큰 값을갖는 노드 즉, Inorder Successor 노드를 찾아라.

Input: root = [5,3,6,2,4,null,null,1], p = 3
Output: 4

Input: root = [5,3,6,2,4,null,null,1], p = 4
Output: 5

Input: root = [5,3,6,2,4,null,null,1], p = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.

해결 아이디어

• 모든 노드를 순회해서 찾을수도 있을것이다. 하지만 이진트리는 탐색시간이 각 단계별로 절반씩 줄어드는 O(logn)을 고려해야한다.

• inorder 순회는 트리의 자식으로 내려갈수록 점점 더 바로 다음 큰 값, 혹은 바로 다음 작은값을 찾을 수 있게 된다.

• if root > p 인경우
  left는 모두 root보다 작음 따라서 root 가 successor가 될 가능성이 있음.

• if root == p
  successor는 root 자신 보다 큰 right에 있을가능성이 존재하기에 right로 이동

• if root < p
  마찬가지로 successor는 p보다 큰값이 기에 right에 있을 가능성있음. right로 이동.

풀이

class Solution {
public:
    TreeNode *succ;
    TreeNode* p_node;
    void travel(TreeNode* root) {
        if (!root)
            return;
        if (root->val > p_node->val) {
            succ = root;
            travel(root->left);
        } else {
            travel(root->right);
        }
    }
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        p_node = p;
        travel(root);
        return succ;
    }
};