难—（java版剑指offer）JZ8 二叉树的下一个结点（两种方法）

//方法一：直接找下一个节点
/*
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) {
        //把中序下一结点归为几种类型：
        //1、有右子树，下一结点是右子树中的最左结点，例如 B，下一结点是 H

        //2、无右子树，且结点是该结点父结点的左子树，
        //则下一结点是该结点的父结点，例如 H，下一结点是 E

        //3、无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，
        //直到找到某个结点是其父结点的左子树，如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。
        //例如 I，下一结点是 A；例如 G，并没有符合情况的结点，所以 G 没有下一结点


        // 1.某个节点的右子树不为空
        if (pNode.right != null) {    //若某个节点的右子树不为空
            TreeLinkNode pRight = pNode.right;    //定义一个右子树的根节点pRight
            while (pRight.left != null) {     //当该根节点的的左子树不为空
                pRight = pRight.left;    //将左子树的根节点赋给pRight，为循环做准备，直到找到某个节点的右子树最左的节点
            }
            return pRight;    //返回某个节点的下一个值
        }
        // 2.某个节点的右子树为空
        //2.1若某个节点的的父节点不为空且其是父节点的左子树的根节点
        //那么某个节点的父节点就是它的下一个节点
        if (pNode.next != null && pNode.next.left == pNode) {    
            return pNode.next;
        }
        // 2.某个节点的右子树为空
        // 2.2若某个节点的父节点不为空且其是父节点的右子树的根节点
        if (pNode.next != null) {
            TreeLinkNode pNext = pNode.next;    //定义一个父节点pNext
            //当满足：其父节点的父节点不为空且其父节点是其父节点的父节点的右子树，一直循环
          //G点最后是因为pNext.next != null这个条件不满足，导致输出pNext.next为空
          //而H点是因为不满足pNext.next.right == pNext这个条件，输出pNext.next
            while (pNext.next != null && pNext.next.right == pNext) {    
                pNext = pNext.next;    //父节点的父节点赋给pNext
            }
            return pNext.next;
        }
        return null;    //以上条件均不满足，返回null
    }
}

//方法二：找根节点->中序遍历，排好序->遍历查找！
/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
import java.util.*;
public class Solution {
    //给了二叉树的某个结点，且二叉树存储着指向父结点的指针（next）
    //先找到根节点，再对树进行中序遍历，最后根据中序遍历结果找到给定结点的下一结点
    static ArrayList<TreeLinkNode> list = new ArrayList<>();    //定义一个静态数组列表，用于存放中序遍历后的数据。
    //注意数组列表的类型<TreeLinkNode>，因为下面方法的返回值的类型是<TreeLinkNode>
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        //1、找根节点
        TreeLinkNode par = pNode;    //定义树链表节点par指向某个节点，pNode不能修改，只能新建一个，替他修改
        while(par.next != null){    //当父节点不为空，继续遍历父节点的父节点，直到找到整棵树的根节点
            par = par.next;
        }
        
        //2、中序遍历
        InOrder(par);    //中序遍历
        
        //3、在列表中找出相同的值，并且找出其下一个值
        for(int i=0;i<list.size();i++){    // 遍历
            if(pNode == list.get(i)){    //找到相等的
                
                //三目运算：条件判断，成立则运行冒号前的话，不成立则运行后面的
                return i == list.size()-1?null:list.get(i+1);      //避免输入的某个节点pNode是排在最后的一个值
            }
        }
        return null;
    }
    //中序遍历方法
    void InOrder(TreeLinkNode pNode){
        if(pNode!=null){
            InOrder(pNode.left);    //递归左边中序遍历
            list.add(pNode);    //把节点引用，按中序遍历放入list列表中
            InOrder(pNode.right);    //递归右边中序遍历
        }
    }
}