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

package main

/*
type TreeLinkNode struct {
    Val int
    Left *TreeLinkNode
    Right *TreeLinkNode
    Next *TreeLinkNode
}
*/
/*
       A
	/     \
   B       C
  / \     / \
 D    E  F   G
     / \
    H   I
*/
// 中序 D -> B -> H -> E -> I -> A -> F -> C -> G -> nil
// 有右子树，下一结点是右子树中的最左结点 B -> H
// 无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点 H -> E
// 无右子树，且结点是该结点父结点的右子树，则一直沿着父结点追朔，直到找到某个结点是其父结点的左子树
// 			 如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点 I -> A，不存在 G -> nil

func GetNext(pNode *TreeLinkNode) *TreeLinkNode {
	if pNode == nil {
		return nil
	}

	// 有右子树
	if pNode.Right != nil {
		pNode = pNode.Right
		for pNode.Left != nil {
			pNode = pNode.Left
		}

		return pNode
	}

	// 无右子树
	for pNode.Next != nil {
		if pNode == pNode.Next.Left {
			return pNode.Next
		}
		// 一直沿着父结点追朔
		pNode = pNode.Next
	}

	return nil
}