設(shè)計(jì)一個(gè)算法簸州，找出二叉搜索樹中指定節(jié)點(diǎn)的“下一個(gè)”節(jié)點(diǎn)（也即中序后繼）缠借。
如果指定節(jié)點(diǎn)沒有對(duì)應(yīng)的“下一個(gè)”節(jié)點(diǎn)，則返回null跳夭。
示例 1:
輸入: root = [2,1,3], p = 1
2
/
1 3
輸出: 2
二叉搜索樹的性質(zhì)：
左子樹都比當(dāng)前節(jié)點(diǎn)的值型吭病；
右子樹都比當(dāng)前節(jié)點(diǎn)的值大币叹。
我們要找比指定節(jié)點(diǎn)p大的下一個(gè)節(jié)點(diǎn)的润歉，那么有以下可能：
當(dāng)前節(jié)點(diǎn)的值 <=<= 指定節(jié)點(diǎn)的值，即 root.val <= p.valroot.val<=p.val颈抚，那么一定要在rootroot的右子樹上找比 pp大的下一個(gè)節(jié)點(diǎn)踩衩。
因?yàn)槲覀円冶?p大的節(jié)點(diǎn)，而此時(shí) root.valroot.val和其左子樹都比 p.valp.val小贩汉，因此左子樹上就不用找了驱富。
package 遞歸;//leetcode submit region begin(Prohibit modification and deletion)
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
class SuccessorLCCI {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if (root == null) return null;
if (root.val <= p.val)
return inorderSuccessor(root.right, p);
TreeNode findLeft = inorderSuccessor(root.left, p);
return findLeft != null ? findLeft : root;
}
// 遞歸.TreeNode node;
// List<Integer> list = new ArrayList();
// public void getCurNode(遞歸.TreeNode node, int find) {
// if (node != null) {
// if (node.left != null) {
// getCurNode(node.left, find);
// }
// if (find != -1) {
// if (find == node.val) {
// this.node = node;
// return;
// }
// }
// list.add(node.val);
// if (node.right != null) {
// getCurNode(node.right, find);
// }
// }
// }
//
// public 遞歸.TreeNode inorderSuccessor(遞歸.TreeNode root, 遞歸.TreeNode p) {
// getCurNode(root, p.val);
// int index = -1;
// for (int i = 0; i < list.size(); i++) {
// if (p.val == list.get(i)) {
// index = i;
// break;
// }
// }
// index++;
// if (index > list.size()-1) {
// return null;
// }
// getCurNode(root, list.get(index));
// return node;
// }
public static void main(String[] args) {
SuccessorLCCI so = new SuccessorLCCI();
TreeNode a1 = new TreeNode(2);
// 遞歸.TreeNode a2 = new 遞歸.TreeNode(1);
TreeNode a3 = new TreeNode(3);
// 遞歸.TreeNode a4 = new 遞歸.TreeNode(1);
// 遞歸.TreeNode a5 = new 遞歸.TreeNode(4);
// 遞歸.TreeNode a6 = new 遞歸.TreeNode(2);
// a1.left = a2;
a1.right = a3;
// a2.left = a4;
// a2.right = a5;
// a4.right = a6;
TreeNode a = so.inorderSuccessor(a1, a3);
int b = 1;
}
}
//leetcode submit region end(Prohibit modification and deletion)
