题解 | #二叉树的下一个结点#

/**
 * class TreeLinkNode(var `val`: Int) {
 *     var left: TreeLinkNode? = null
 *     var right: TreeLinkNode? = null
 *     var next: TreeLinkNode? = null
 * }
 */
object Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param pNode TreeLinkNode类 
        * @return TreeLinkNode类
    */
    fun GetNext(pNode: TreeLinkNode?): TreeLinkNode?  {
        if (pNode == null) return pNode
        if (pNode!!.right == null) {
            var father = pNode!!.next
                        //如果目标节点右子树为空，获取父节点，如果目标节点刚好是父节点的左子树那么按照中序遍历下一个遍历的刚好是父节点
            if (father != null && father.left == pNode) return father
                        //递归寻找一个目标节点在该节点的左子树的节点
            var grand = father?.next
            while (grand != null && grand.left != father) {
                father = grand
                grand = grand?.next
            }
            return  grand
        }
                //右子树不为空，则下一个节点就是右子树的最左的节点
        return getLeft(pNode!!.right!!)
    }
    
    private fun getLeft(root: TreeLinkNode): TreeLinkNode {
        if (root.left == null) return root
        return getLeft(root.left!!)
    }
}