題目：給定一顆二叉樹和其中的一個節(jié)點，如何找出中序遍歷的下一個節(jié)點？樹中的節(jié)點除了有兩個分別指向左泛豪、右節(jié)點的指針，還有一個指向父節(jié)點的指針。
分析
如果一個節(jié)點有右子樹诡曙，那么它的下一個節(jié)點就是右子樹中最左子節(jié)點吕粹。如下圖節(jié)點b的下一個節(jié)點就是右子樹的最左節(jié)點「h」。節(jié)點「a」的下一個節(jié)點就是「f」岗仑。
如果一個節(jié)點沒有右子樹匹耕，且節(jié)點是它父節(jié)點的左子節(jié)點，那么它的下一個節(jié)點就是它的父節(jié)點荠雕。如下圖「d」的下一個子節(jié)點是「b」稳其，節(jié)點「f」的下一個節(jié)點是「c」。
如果一個節(jié)點又沒有右子樹炸卑，且它還是父節(jié)點的右子節(jié)點既鞠。那么我們就要沿著指向父節(jié)點的指針一直向上遍歷，直到找到一個是它父節(jié)點的左子節(jié)點的節(jié)點盖文。如果存在這樣的節(jié)點嘱蛋。那么這個節(jié)點的父節(jié)點就是我們要找的下一個節(jié)點。如圖： 為了找到節(jié)點i的下一個節(jié)點五续，我們需要向上遍歷洒敏，先達到節(jié)點「e」，由于「e」節(jié)點是「b」節(jié)點的右節(jié)點疙驾，不符合凶伙，繼續(xù)向上到「b」節(jié)點，「b」節(jié)點是「a」節(jié)點的左節(jié)點它碎。所以「b」的父節(jié)點「a」就是我們要找的下一個節(jié)點函荣。同理 「g」節(jié)點的下一個節(jié)點，首先找到「c」扳肛，「c」是「a」的右子節(jié)點傻挂，不符合要求，繼續(xù)向上到「a」挖息，「a」節(jié)點沒有父節(jié)點金拒，因此「g」節(jié)點的下一個節(jié)點為空。
代碼實現(xiàn)
func findNextTreeNode(_ node: TreeNode?) -> TreeNode? {
guard let node = node else {
return nil
}
var nextNode :TreeNode?
// 如果節(jié)點有右子樹,返回右子樹的最左子節(jié)點
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
// 節(jié)點不是父節(jié)點的左子節(jié)點旋讹，且父節(jié)點是右子節(jié)點一直向上遍歷殖蚕，則到節(jié)點的父節(jié)點為左子節(jié)點或者為nil
while parentNode != nil && parentNode?.right?.val == currentNode?.val {
currentNode = parentNode
parentNode = parentNode?.parent
}
// 節(jié)點是父節(jié)點的左子節(jié)點,則下一個節(jié)點就是父節(jié)點
nextNode = parentNode
}
return nextNode
}
