剑指Offer-57 二叉树的下一个结点
题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
输入：暂无
输出：暂无
解析
在本题给出的二叉树中，其中的数的结点也是一个特殊的数据结构，代码如下
1public class TreeLinkNode {
2 int val;
3 TreeLinkNode left = null;
4 TreeLinkNode right = null;
5 TreeLinkNode next = null;
6
7 TreeLinkNode(int val) {
8 this.val = val;
9 }
10}
我们可以看到，除了普通二叉树结点都有的左右孩子的引用之外，还额外有一个next引用，在本题中也给出了是指向了本结点的父结点。
首先遍历的规则是中序遍历，所以是左、根、右的一种遍历。
结合图，我们可发现分成两大类：1、有右子树的，那么下个结点就是右子树最左边的点；（eg：D，B，E，A，C，G） 2、没有右子树的，也可以分成两类，a)是父节点左孩子（eg：N，I，L） ，那么父节点就是下一个节点 ； b)是父节点的右孩子（eg：H，J，K，M）找他的父节点的父节点的父节点...直到当前结点是其父节点的左孩子位置。如果没有eg：M，那么他就是尾节点。
1public class Solution {
2 public TreeLinkNode GetNext(TreeLinkNode pNode){
3 if(pNode==null)
4 return null;
5 if(pNode.left==null&&pNode.right==null){
6 if(pNode.next==null)
7 return null;
8 else{
9 if(pNode.next.right==pNode){
10 TreeLinkNode temp=pNode.next;
11 if(temp.next==null||temp.next.right==temp)
12 return null;
13 while(temp.next!=null)
14 temp=temp.next;
15 return temp;
16 }else if(pNode.next.left==pNode){
17 return pNode.next;
18 }
19 }
20 }
21 if(pNode.right!=null){
22 TreeLinkNode temp=pNode.right;
23 while(temp.left!=null)
24 temp=temp.left;
25 return temp;
26 }else{
27 return pNode.next;
28 }
29 }
30}