题目描述
给定一颗二叉树和其中的一个节点，如何找出中序遍历的下一个节点？树中节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。
解题思路:
- 以如下二叉树为例，中序遍历为{d,b,h,e,i,a,f,c,g}，给定的二叉树节点用A表示。
a
/ \
b c
/ \ / \
d e f g
/ \
h i
- 如果A有右子树，那它的下一个节点是右子树里最左节点。
- 如果A没有没有右子树，并且A是A的父节点的左节点，那它的下一个节点就是他的父节点。
- 如果A没有没有右子树，并且A是A的父节点的右节点，则沿着父节点的指针向上遍历，直到当前节点不是其父节点的右节点。则当前节点的父节点即为A的下一个节点。
代码
static class TreeNode1{
String value;
TreeNode1 left;
TreeNode1 right;
TreeNode1 parent;
TreeNode1(String val){
this.value = val;
}
@Override
public String toString() {
return value;
}
}
TreeNode1 getInOrderNext(TreeNode1 curNode){
if (curNode == null) {
return null;
}
if (curNode.right != null) {
// 存在右子树，那它的下一个节点是右子树里最左节点。
TreeNode1 tmp = curNode.right;
while (tmp.left != null) {
tmp = tmp.left;
}
return tmp;
}
if (curNode.parent != null) {
if (curNode == curNode.parent.left) {
// 如果curNode没有没有右子树，并且curNode是curNode的父节点的左节点，那它的下一个节点就是他的父节点。
return curNode.parent;
}
TreeNode1 tmp = curNode;
// 如果curNode没有没有右子树，并且curNode是curNode的父节点的右节点，则沿着父节点的指针向上遍历，直到tmp节点不是其父节点的右节点。
// 则tmp节点的父节点即为curNode的下一个节点。
while (tmp.parent != null && tmp.parent.right == tmp) {
tmp = tmp.parent;
}
return tmp.parent;
}
return null;
}
