给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示
示例
input1:
{1,2,#,#,3,#,4},4
output1:
1
input2:
{5},5
output2:
"null"
input3：
{8,6,10,5,7,9,11},8
output3：
9
note:这个组装传入的子树根节点，其实就是整颗树，中序遍历{5,6,7,8,9,10,11}，根节点8的下一个节点就是9，应该返回{9,10,11}，后台只打印子树的下一个节点，所以只会打印9，如下图，其实都有指向左右孩子的指针，还有指向父节点的指针，下图没有画出来
思路
本题主要需要熟悉二叉树的中序遍历顺序，在解法上分为两种：暴力破解法和根据中序规律求解
1、暴力破解法首先根据当前结点寻找整棵树的根结点，接着根据整棵树的根结点获取中序遍历的结果，最后在中序结果中找到当前结点，并返回下一个结点
import java.util.ArrayList;
public class Solution {
ArrayList arr = new ArrayList<>();
public void in_order(TreelinkNode node){
if(node == null) return;
in_order(node.left);
arr.add(node);
in_order(node.right);
}
public TreelinkNode GetNext(TreelinkNode pNode) {
//寻找整棵树的根结点
TreelinkNode tmp = pNode;
while(tmp.next != null) tmp = tmp.next;
//根据整棵树的根结点获取中序遍历的结果
in_order(tmp);
//在中序结果中找到当前结点，并返回下一个结点
for(int i = 0; i < arr.size(); i++){
if(arr.get(i).val == pNode.val)
return i == arr.size() - 1? null : arr.get(i+1);
}
return null;
}
}
2、根据中序规律求解
中序遍历的顺序是：左子树、根结点、右子树。
根据当前结点可以分为以下几种情况：
（1）当前结点有右子树，那么直接返回其右子树中序遍历的第一个元素：即右子树最左侧的元素。如图中的B，返回D；图中的A，返回F
（2）当前结点无右子树，分为两种情况
- 该结点位于其父结点的左子树。根据中序遍历规则，返回其父结点。如图中的H，返回B；I返回H
- 该结点位于其父结点的右子树。若当前结点的父结点处于某个子树的右侧分支，则沿着根的方向一直找到该子树的根结点，返回这个根结点的父结点。如图中的D，返回B的根结点A；图中的C，返回null
public class Solution {
public TreelinkNode GetNext(TreelinkNode pNode) {
if(pNode == null) return null;
//有右子树，返回右子树的最左侧结点
if(pNode.right != null){
TreelinkNode tmp = pNode.right;
while(tmp.left != null) tmp = tmp.left;
return tmp;
}
//无右子树,，分为两种情况：该结点是该结点父结点的左子树或者右子树
//（1）左子树，按照中序的规则，左-中-右，因此直接返回其父结点
if(pNode.next != null && pNode.next.left == pNode) return pNode.next;
//（2）右子树，
if(pNode.next != null && pNode.next.right == pNode){
TreelinkNode tmp = pNode.next;
while(tmp.next != null && tmp.next.right == tmp) tmp = tmp.next;
return tmp.next;
}
return null;
}
}
**简化写法：**由于中序的遍历顺序是：左-根-右，因此当前结点无右节点时，它作为右子树时的根结点肯定已经倍访问过了，所以只需要将其作为右子树的方向沿着根寻找结点，直到这个结点位于其父结点的左子树，那么其父结点就是中序遍历的下一个结点
public class Solution {
public TreelinkNode GetNext(TreelinkNode pNode) {
if(pNode == null) return null;
//有右子树，返回右子树的最左侧结点
if(pNode.right != null){
TreelinkNode tmp = pNode.right;
while(tmp.left != null) tmp = tmp.left;
return tmp;
}
//无右子树，沿着根结点来寻找当前结点位于其根结点的左子树时，返回该根结点的父结点
while(pNode.next != null && pNode.next.left != pNode) pNode = pNode.next;
return pNode.next;
}
}
