剑指offer—面试题8: 二叉树的下一个节点

题目：给定一颗二叉树和其中的一个节点，如何找出中序遍历的下一个节点？树中的节点除了有两个分别指向左、右节点的指针，还有一个指向父节点的指针。

分析

如果一个节点有右子树，那么它的下一个节点就是右子树中最左子节点。如下图节点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
    }