二叉树的下一个节点

题目描述

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

/*
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
    }

总结

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