给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null; //觉得改成parent更好一点
TreeLinkNode(int val) {
this.val = val;
}
}这个题目我在另一篇博客在一颗二叉树中寻找一个结点的后继结点或者前驱节点已经详细介绍。
分三种情况。不赘述。
public class Solution {
// next 最好写成 parent
public TreeLinkNode GetNext(TreeLinkNode pNode) {
if (pNode == null) return null;
if (pNode.right != null) return getMostLeft(pNode.right); // 答案是: 右孩子的最左节点
if (pNode.next != null && pNode.next.left != null && pNode.next.left == pNode) // 答案是: 父亲
return pNode.next;
while (pNode.next != null && pNode.next.right != null && pNode.next.right == pNode) //答案是不断的往上找
pNode = pNode.next;
return pNode.next;
}
//获得node的最左下角节点
public TreeLinkNode getMostLeft(TreeLinkNode node) {
while (node.left != null) node = node.left;
return node;
}
}