题目
给定一个二叉树与其中一个节点（目标节点），找到中序遍历中的下一个节点(子节点中包含父节点的引用)
题解
解法1：从根节点中序遍历，遍历至目标节点，继续向下遍历一次，取得结果。
此解法缺点就是没有很好的利用子节点中的父节点属性，时间复杂度相对较高
解法2：
- 中序遍历 秉承着左根右的规律，即存在两种情况
- 存在右节点
- 不存在右节点
- case1：存在右节点
存在右节点，我们只要找右节点的最左孩子即可（包括它自己） - case2：不能存在右节点
即我们遍历的节点已经达到该分支的右边界，那么我们只要反向找到该节点的父节点。- 如果父节点 是爷爷节点（父节点的父节点）左孩子，即代表当前左已经全部遍历完成，该遍历根了，爷爷节点即是下一个结果。
- 如果父节点 是爷爷节点的右孩子，那么继续向上找，即父亲节点作为当前节点重复case2逻辑。
public DetailTreeNode findNextInOrder(DetailTreeNode root, DetailTreeNode node) {
if (node == null || root == null) return null;
DetailTreeNode data;
if (node.getRight() != null) {
data = node.getRight();
while (data.getLeft() != null) {
data = data.getLeft();
}
return data;
}
data = node.getParent();
while (data != null && node != data.getLeft()) {
node = data;
data = data.getParent();
}
return data;
}
源码: 剑指offer4J
