LeetCode 剑指 Offer 08. 二叉树的下一个节点

题目：二叉树的下一个节点

给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。（树的后继）

注意：

• 如果给定的节点是中序遍历序列的最后一个，则返回空节点;
• 二叉树一定不为空，且给定的节点一定不是空节点；

解题思路

二叉树的中序遍历：{ [左子树], 根节点, [右子树] }

如图所示二叉树的中序遍历：D, B, H, E, I, A, F, C, G

分三种情况：

1. 如果该节点有右子树，那么下一个节点就是其右子树中最左边的节点；

2. 如果该节点没有右子树，且是其父节点的左子节点，那么下一个节点就是其父节点；

3. 如果该节点没有右子树，且是其父节点的右子节点，沿着父指针一直向上，直到找到一个是它父节点的左子节点的节点，如果这样的节点存在，那么这个节点的父节点即是所求。

例如：

• 情况 1：图中节点 B 的下一个节点是节点 H；

• 情况 2：图中节点 H 的下一个节点是节点 E；

• 情况 3：图中节点 I 的下一个节点是节点 A。

时空复杂度：O(height)，其中 height 是二叉树的高度， 空间复杂度：O(1)

func inorderSuccessor(p *TreeNode) *TreeNode {
	//右子树存在 右子树最左边的结点
	if(p.Right != nil){
		p = p.Right
		for(p.Left != nil){
			p = p.Left
		}
		return p
	}
	//右子树不存在 只有左子树
	for(p.Father != nil){
		//p不是根节点
		if(p == p.Father.Left) {  //如果是父节点的左子树
			return p.Father  //返回父节点
		}
		p = p.Father   //继续往上找
	}
	return nil
}