题目描述

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

/*public class TreeLinkNode {    int val;    TreeLinkNode left = null;    TreeLinkNode right = null;    TreeLinkNode next = null;    TreeLinkNode(int val) {        this.val = val;    }}*/

思路

要求中序遍历的下一个节点，那么首先需要对节点进行分类，哪些节点的下一个节点是是父节点，哪些节点的下一个节点与子节点有关


上图将节点分成了三类，实际上我们可以根据红色箭头的指向，分成两类，紫色和橙色的节点为一类，蓝色的为一类

  • 紫色和橙色节点：共同点都是本身没有右孩子。

    • 如果本身又是父节点的左孩子，那么下一个节点就是父节点
    • 如果本身不是父节点的左孩子，那么继续寻找，直到找到一个祖先是某个节点a的左孩子，那么下一个节点就是节点a

  • 蓝色节点：该节点有右孩子

    • 该节点的右孩子没有左孩子：下一个节点就是该节点的右孩子
    • 该节点的右孩子还有左孩子：下一个节点就是该节点的右孩子的左孩子，如果左孩子还有左孩子，就继续遍历，直到遇到最后一个左孩子就是下一个节点

感觉文字描述有点啰嗦，下面直接看代码，总而言之就是将节点分成了两大类（根据有没有右孩子），然后每个大类又分成了两个小类

 public TreeLinkNode GetNext(TreeLinkNode pNode)    {        if(pNode==null) return null;        if(pNode.right!=null){    //如果有右子树，则找右子树的最左节点            pNode = pNode.right;            while(pNode.left!=null) pNode = pNode.left;            return pNode;        }        while(pNode.next!=null){ //没右子树，则找第一个当前节点是父节点左孩子的节点            if(pNode.next.left==pNode) return pNode.next;            pNode = pNode.next;        }        return null;   //退到了根节点仍没找到，则返回null    }

总结

本题的关键点在于画出中序遍历的图，发现规律，将节点进行分类
欢迎关注：小秋的博客