题目:
给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
思路:
根据中序遍历的思路然后进行归纳, 分为两种类型有右子树,无右子树
1.有右子树的节点的下一个节点,是当前节点右子树最左节点.
2.无右子树的节点,如果当前节点是父节点的左子节点,下一个节点就是父亲节点.
3.无右子树的节点, 如果当前节点是父亲节点的右子节点,下一个节点就是父亲节点的下一个节点...
4.其他情况的下一个节点就为null
代码:
public class GetNext
{
/**
* @param pNode
* @return
*/
public TreeLinkNode GetNext(TreeLinkNode pNode){
if(pNode == null)
return null;
if(pNode.right != null){
pNode = pNode.right;
while(pNode.left != null)
pNode = pNode.left;
return pNode;
}
while(pNode.next != null){
if(pNode.next.left == pNode){
return pNode.next;
}
pNode = pNode.next;
}
//遍历结束还不符合这两种条件的1.是最后的节点没有父节点 2.是不存在这个节点
return null;
}
}