Leetcode - 510. Inorder Successor in BST II

문제

BST가 주어지고 트리 내의 한 노드의 포인터가 주어진다.(root노드가 주어지는게 아님주의). 그 노드의 Inorder Successor를 리턴하라. 각 노드는 parent 노드를 가지고 있다.

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

유사문제는 : 285. Inorder-Successor-in-BST

해결 아이디어

• 풀이1:
  첫번째로 조금 Naive한 접근법: root를 먼저 찾고 그뒤 succeessor를 찾는다.

풀이 1

// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
};
*/

class Solution {
public:
    Node *succ = NULL;
    Node *getroot(Node *node) {
        if (!node->parent)
            return node;
        return getroot(node->parent);
    }
    void travel(Node *root, Node *node) {
        if (!root)
            return;
        if (root->val > node->val) {
            succ = root;
            travel(root->left, node);
        } else {
            travel(root->right, node);
        }
    }
    Node *inorderSuccessor(Node* node) {
        Node *root = getroot(node);
        cout << root->val;
        travel(root, node);
        return succ;
    }
};