8.md

二叉树的下一个结点

题目

给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示

要求：空间复杂度 O(1)，时间复杂度 O(n)

输入描述： 输入分为2段，第一段是整体的二叉树，第二段是给定二叉树节点的值，后台会将这2个参数组装为一个二叉树局部的子树传入到函数GetNext里面，用户得到的输入只有一个子树根节点

返回值描述： 返回传入的子树根节点的下一个节点，后台会打印输出这个节点

示例

示例: 输入:{8,6,10,5,7,9,11},8 返回:9 解析:这个组装传入的子树根节点，其实就是整颗树，中序遍历{5,6,7,8,9,10,11}，根节点8的下一个节点就是9，应该返回{9,10,11}，后台只打印子树的下一个节点，所以只会打印9，如下图，其实都有指向左右孩子的指针，还有指向父节点的指针，下图没有画出来

思路

大力出奇迹

• 根据给出的结点求出整棵树的根节点【一直找 Next 直到 nil】
• 根据根节点递归求出树的中序遍历，存入数组
• 在数组中查找当前结点，则当前结点的下一结点即为所求

最优解法[找规律分类处理]

1. 当前结点是父节点的左孩子，下一个是父节点
2. 当前结点是父节点的右孩子，下一个是爷爷节点，本质还是[1]那一类
3. 当前结点的下一个是右孩子结点的最左孩子结点，如果右孩子结点没有左孩子就是右孩子结点
4. 最尾结点，Next 是 nil

• [1]和[2]的共同点是右节点为空
• 所以先梳理[3]的，找到右节点，一直往左捋
• 然后一直沿着 Next 往上找
• 如果父节点的左节点是自己的，说明是情形[1]返回父节点，否则向上回溯
• 剩下就是情况[4]的，返回 nil

实现

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

	if pNode.Right != nil {
		pNode = pNode.Right
		for pNode.Left != nil {
			pNode = pNode.Left
		}
		return pNode
	}

	for pNode.Next != nil {
		if pNode.Next.Left == pNode {
			return pNode.Next
		}
        // 向上回溯
		pNode = pNode.Next
	}

	return nil
}