题目描述

给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。

注意：

如果给定的节点是中序遍历序列的最后一个，则返回空节点;
二叉树一定不为空，且给定的节点一定不是空节点；

golang 代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 *     Father *TreeNode
 * }
 */
func inorderSuccessor(p *TreeNode) *TreeNode {
    //p有右子树，则右子树最左节点为下一个节点
    if p.Right != nil{
        p = p.Right
        for p.Left != nil {
            p = p.Left
        }
        return p
    }
    //p没有右子树，且p是父节点右子树，则向父节点移动，直到p没有父节点或者p是父节点左子树
    for p.Father != nil && p.Father.Right == p {
        p = p.Father
    }
    //p有父节点，说明p是父节点左子树，返回父节点
    if p.Father != nil {
        return p.Father
    }
    //p没有父节点
    return nil
}