Leetcode每日一题：22/05/16：面试题04.06：后继者

设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。如果指定节点没有对应的“下一个”节点，则返回null。

思路：二叉搜索树中序遍历有序，因此：中序后继节点，也就是比它大的最小的一个节点，

• 若节点存在右子树，则该最小值为右子树的最左叶子节点
• 若不存在右子树，则该最小值为左子树的父节点
• 若不存在则null

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode parent = null, node = root;
        if (node == null) {
            return null;
        }
        while (node != null) {
            if (node.val > p.val) {//当前节点值大于指定节点值，说明指定节点在当前节点的左子树中
                parent = node;//parent为左子树父节点
                node = node.left;//进入左子树
            } else if (node.val < p.val) {//当前节点值小于指定节点值，说明指定节点在当前节点的右子树中
                node = node.right;//进入右子树
            } else if (node.right != null) {//此时node.val=p.val，若右子树非空，则进入右子树
                node = node.right;
                while (node.left != null) {//找到右子树中最左叶子节点
                    node = node.left;
                }
                return node;
            } else {//node.val = p.val且右子树为空
                return parent;
            }
        }
        return parent;
    }
}