😑285 inorder successor in BST

https://leetcode.com/problems/inorder-successor-in-bst/

感觉这种办法最直观，做inorder traverse并keep track of current index，如果找到了就看下一个index的node是哪个，要注意idx应该是全局变量，同时find不能有返回值，因为是不能立刻返回的

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int idx = -1;
    private int cnt = 0;
    private TreeNode ans = null;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        find(root, p);
        return ans;
    }
    private void find(TreeNode root, TreeNode p) {
        if (root == null) return;
        find(root.left, p);
        cnt++;
        if (root.val == p.val) idx = cnt;
        if (idx > 0 && idx + 1 == cnt) ans = root;
        find(root.right, p);
    }
}

或者可以利用BST特性剪枝

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int idx = -1;
    private int cnt = 0;
    private TreeNode ans = null;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        find(root, p);
        return ans;
    }
    private void find(TreeNode root, TreeNode p) {
        if (root == null) return;
        if (root.val > p.val) find(root.left, p);
        cnt++;
        if (root.val == p.val) idx = cnt;
        if (idx > 0 && idx + 1 == cnt) ans = root;
        find(root.right, p);
    }
}