现在有一种新的二叉树节点类型如下：

1
2
3
4
5
6
7
8
9
public class Node {
	public int value;
	public Node left;
	public Node right;
	public Node parent;
	public Node(int data) {
		this.value = data;
	}
}

该结构比普通二叉树节点结构多了一条指向父节点的parent指针。假设有一棵Node类型的节点组成的二叉树，树中每个节点的parent指针都正确的指向自己的父节点，头节点的parent指向null。只给一个在二叉树中的某个节点node，请实现返回node的后继节点的函数。在二叉树的中序遍历的序列中，node的下一个节点叫做node的后继节点。
例如，下图的二叉树：

1
2
3
4
5
6
7
     __________6__________
   	  /                 \ 
  ___3___             ___9___
 /       \           /       \
1__       4__     __8        10
   \         \   /
   2          5  7

中序遍历的结果为：1，2，3，4，5，6，7，8，9，10
所以节点1的后继为节点2，节点2的后继为节点3，…，节点10的后继为null

思路

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public int find(Node node){
		//叶子节点
		if(node.left == null && node.right == null ){
			//找parent到parent的右孩子不是自己或者不存在
			return parent(node);
		}else{
			//非叶子结点
			if(node.left !=null){
				//右孩子存在，返回右孩子的最左
				return left(node.right);
			}else{
				//右孩子 不存在，返回parent
				return node.parent.value;
			}
			
		}
	}
	
	public int left(Node node){
		//找左孩子
		while(node.left != null){
			left(node.left);
		}
		return node.value;
	}
	
	public int parent(Node node){
		if(node.parent != null){
			if(node.parent.right == null){
				return node.parent.value;
			}else{
				while(node.parent.right == node){
					parent(node.parent);
				}
				return node.parent.value;
			}
			
		}else{
			return -1;
		}
	}