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

package main

/*
type TreeLinkNode struct {
    Val int
    Left *TreeLinkNode
    Right *TreeLinkNode
    Next *TreeLinkNode
}
*/

// 分三种情況
// 1. 有右子树，则下一节点是右子树的最左节点
// 2. 无右子树，且该节点是其父节点的左子树，则下一节点是父节点
// 3. 无右子树, 且该节点是其父节点的右子树，则一直沿着父节点往上找，直到找到该节点是其父节点的右子树，则下一节点是该节点的父节点

func GetNext(pNode *TreeLinkNode) *TreeLinkNode {
	if pNode == nil {
		return nil
	}
	
	// 1. 有右子树，则下一节点是右子树的最左节点
	if pNode.Right != nil {
		pNode = pNode.Right
		// 找到最左节点
		for pNode.Left != nil {
			pNode = pNode.Left
		}
		return pNode
	}
	
	// 无右子树，则一直往上找父节点
	for pNode.Next != nil {
		// 返回条件为： pNode 的父节点的左节点等于该节点本身
		if pNode.Next.Left == pNode {
			return pNode.Next
		}
		// 一直往上找父节点
		pNode = pNode.Next
	}
	
	return nil
}