【二叉树】剑指offer 8 二叉树的下一个结点

描述

给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示

题解

这题需要对各种情况分类讨论，一共有三种情况

• 第一种：如果这个节点的右孩子不为空，根据中序遍历的特点，它的下一个节点是它的右孩子的最左边的孩子
  
• 第二种：如果这个节点是其父亲的左孩子，根据中序遍历的特点，它的下一个节点就是其父亲（注意如果父亲为null，则该节点是根节点，此时返回null）
  
• 第三种：最复杂的一个情况，该节点为其父亲的右孩子，此时需要向上找到一个祖先节点A，A是其父亲的左孩子（即回到了第二种情况），这个情况可以通过画图分析得出，例如下图中的节点4，它的下一个节点为3的父节点5，因为3是其父节点5的左孩子
  
  

所有代码

public class Solution {

    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        // 1. 右孩子不空，则找到它右孩子的最左孩子
        if (pNode.right != null) {
            pNode = pNode.right;
            // 找到最左的节点
            while (pNode.left != null)
                pNode = pNode.left;
            return pNode;
        }

        TreeLinkNode parent = pNode.next;
        if (parent == null)
            return null;

        // 2. 右孩子为空，且是父亲的左孩子，父节点为下一节点
        if (parent.left == pNode)
            return pNode.next;

        // 3. 右孩子为空，且是父亲的右孩子
        while (parent != null) {
            // 向上找父亲，直到节点是其父亲的左孩子，即第二种情况
            if (parent.left == pNode)
                return parent;
            pNode = parent;
            parent = parent.next;
        }
        return null;
    }

    public static void main(String[] args) {
        TreeLinkNode r = new TreeLinkNode(1);
        r.left = new TreeLinkNode(2);
        r.left.next = r;

        TreeLinkNode pnow = r.left;
        pnow.right = new TreeLinkNode(3);
        pnow.right.next = pnow;

        pnow = pnow.right;

        pnow.right = new TreeLinkNode(4);
        pnow.right.next = pnow;
        TreeLinkNode res = new Solution().GetNext(pnow.right);
        System.out.println(res.val);
    }
}