【面试题57-二叉树的下一个结点】

剑指offer第五十七题。

题目描述

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

解题思路

我们对于中序排序的规则已经很熟悉，下面图示:

我们从这个图上可以看到，找下一个节点是可以分为几种情况的。

第一种情况，就是一个节点有右子树。比如要求节点B的下一个节点，其实是找到它的右子树的最左孩子，就是G节点。

第二种情况，就是一个节点没有右子树，此时又可以分为两种情况。

对于G这个节点来说，没有右子节点了，它的父亲节点是E，G是E的左子节点，即E的左子节点是G，那么G的下一个节点就是E。

对于E这个节点来说，也没有右子节点，它的父亲节点是B，此时E是B的右子节点，根据实际情况来说，E的下一个节点绝对不是B，因为E是B的右子节点，根据中序遍历的规则，此时肯定是先遍历B再遍历E，所以B肯定在E的前面，而不是后面，所以我们还需要再往上找父亲节点，此时B的父亲节点为A，B为A的左子节点，此时根据实际情况，A就是我们要找的E的下一个节点。

所以，对于一个没有右子节点的节点来说，只需要判断它有没有父节点并且是不是父节点的左子节点，是的话，就找到了，不是则要不断地向上找。

如果一直找到根还是找不到，像节点F，那就返回null，因为实际上F节点就是中序遍历的最后一个节点，没有所谓的下一个节点了。

将上面所述转换为图示为：

总之，我们不关心当前节点的左子节点，因为它不在我们的考虑范围内，它必定出现在当前节点的前面。

我们主要就是考虑有没有右子节点，或者没有右子节点的话就考虑父亲节点。有右子节点比较简单，一直找最左边的子节点即可。但是没有右子节点的时候，就需要去查询父亲节点了。理解了这些，程序也就呼之欲出了。

我的答案

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode == null){
            return null;
        } 
        
        //1.判断当前节点是否有右子节点，有则去里面找
        if(pNode.right != null){
            return firstInRightTree(pNode);
        //2.没有右子节点，就需要去父节点找
        }else{
            //3.直到找到符合条件的父节点为止，跳出循环时pNode的父节点符合条件，这个父节点就是我们要的东西
            while(pNode.next != null && pNode.next.left != pNode){
                pNode = pNode.next;
            }
            return pNode.next;
        }
    }
    
    //到右子树中找符合条件的，显然就是找最最最左边的子节点即可
    private TreeLinkNode firstInRightTree(TreeLinkNode pNode){
        TreeLinkNode curr = pNode.right;
        while(curr.left != null){
            curr = curr.left;
        }
        return curr;
    }
}