题目：给定一颗二叉树和其中的一个节点，如何找出中序遍历的下一个节点？树中的节点除了有两个分别指向左、右节点的指针，还有一个指向父节点的指针。
image.png
分析
如果一个节点有右子树，那么它的下一个节点就是右子树中最左子节点。如下图节点b的下一个节点就是右子树的最左节点「h」。节点「a」的下一个节点就是「f」。
如果一个节点没有右子树，且节点是它父节点的左子节点，那么它的下一个节点就是它的父节点。如下图「d」的下一个子节点是「b」，节点「f」的下一个节点是「c」。
如果一个节点又没有右子树，且它还是父节点的右子节点。那么我们就要沿着指向父节点的指针一直向上遍历，直到找到一个是它父节点的左子节点的节点。如果存在这样的节点。那么这个节点的父节点就是我们要找的下一个节点。如图： 为了找到节点i的下一个节点，我们需要向上遍历，先达到节点「e」，由于「e」节点是「b」节点的右节点，不符合，继续向上到「b」节点，「b」节点是「a」节点的左节点。所以「b」的父节点「a」就是我们要找的下一个节点。同理 「g」节点的下一个节点，首先找到「c」，「c」是「a」的右子节点，不符合要求，继续向上到「a」，「a」节点没有父节点，因此「g」节点的下一个节点为空。
代码实现
func findNextTreeNode(_ node: TreeNode?) -> TreeNode? {
guard let node = node else {
return nil
}
var nextNode :TreeNode?
// 如果节点有右子树,返回右子树的最左子节点
if node.right != nil {
var rightNode = node.right
while rightNode?.left != nil {
rightNode = rightNode?.left
}
nextNode = rightNode
}else if node.parent != nil {
var currentNode :TreeNode? = node
var parentNode :TreeNode? = node.parent
// 节点不是父节点的左子节点，且父节点是右子节点一直向上遍历，则到节点的父节点为左子节点或者为nil
while parentNode != nil && parentNode?.right?.val == currentNode?.val {
currentNode = parentNode
parentNode = parentNode?.parent
}
// 节点是父节点的左子节点,则下一个节点就是父节点
nextNode = parentNode
}
return nextNode
}
