题目描述

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

【解决】

① 如果一个结点有右子树，那么它的下一个结点就是它的右子树中的左子结点。也就是说右子结点出发一直沿着指向左子结点的指针，我们就能找到它的下一个结点。

接着我们分析一个结点没有右子树的情形。如果结点是它父节点的左子结点，那么它的下一个结点就是它的父结点。 如果一个结点既没有右子树，并且它还是它父结点的右子结点，这种情形就比较复杂。我们可以沿着指向父节点的指针一直向上遍历，直到找到一个是它父结点的左子结点的结点。如果这样的结点存在，那么这个结点的父结点就是我们要找的下一个结点。

/*

public class TreeLinkNode {     int val;     TreeLinkNode left = null;     TreeLinkNode right = null;     TreeLinkNode next = null;

    TreeLinkNode(int val) {

        this.val = val;     } } */

public class Solution {

    public TreeLinkNode GetNext(TreeLinkNode pNode){         if (pNode == null) return null;         TreeLinkNode target = null;         TreeLinkNode cur = pNode;         if (cur.right != null){//判断是否有右孩子             target = cur.right;             while (target.left != null){                 target = target.left;             }             return target;         }         if (cur.next == null){//判断有没有父节点             return null;         }         if (cur.next.left == cur){//如果是其父节点的左子节点             return cur.next;         }         target = cur.next;//是其父节点的右子节点，向上找其父节点，知道找到是其父节点的左孩子的父节点         while(target.next != null){             if (target == target.next.left){                 return target.next;             }             target = target.next;         }         return null;     } }