剑指offer.二叉树的下一个结点

题目描述

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

思路介绍

最基本的做法当然是把二叉树还原一下，毕竟这个树中结点包含指向父结点的指针。
这里给出一个基于对中序遍历本身的理解的做法。
链接：https://www.nowcoder.com/questionTerminal/9023a0c988684a53960365b889ceaf5e?answerType=1&f=discussion
来源：牛客网

分析：

以这个二叉树为例。中序遍历序列应该是{D,B,H,E,I,A,F,C,G}
那么，经过归纳，可以发现，二叉树中序遍历的下一个结点，一共只有如下三种情况。

1. 有右子树，下一结点是右子树中的最左结点，例如 B，下一结点是 H

2. 无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点，例如 H，下一结点是 E

3. 无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追溯，直到找到某个结点是其父结点的左子树，如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。例如 I，下一结点是 A；例如 G，并没有符合情况的结点，所以 G 没有下一结点

代码：

public class Solution {
 
public TreeLinkNode GetNext(TreeLinkNode pNode) {
     // 1.
     if (pNode.right != null) {
         TreeLinkNode pRight = pNode.right;
         while (pRight.left != null) {
             pRight = pRight.left;//遍历找到右子树的最左结点
         }
         return pRight;
     }
     // 2.
     if (pNode.next != null && pNode.next.left == pNode) {
         return pNode.next;//找到父结点即可
     }
     // 3.
     if (pNode.next != null) {
         TreeLinkNode pNext = pNode.next;
         while (pNext.next != null && pNext.next.right == pNext) {//一直向上遍历直到找到某个结点不是它父结点的右儿子结点，那么他就是要找的左子树
             pNext = pNext.next;
         }
         return pNext.next;//找到这个左子树的父结点即可
     }
     return null;
 }
}