给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。
public class Solution { public TreeLinkNode GetNext(TreeLinkNode pNode){ if(pNode==null)return null; //如果该节点有右节点,则右节点的最左节点即为下一个节点; //本身没有右节点,则向前找父节点,看看有没有父节点是一个左节点 //如果有一个父节点是左节点,那那个父节点的父节点即为答案 //如果没有有一个父节点是左节点,则该节点本身为最后一个 if(pNode.right != null)return leftnode(pNode.right); else return leftroot(pNode); } public TreeLinkNode leftnode(TreeLinkNode p){ while(p.left!=null){ p = p.left; } return p; } public TreeLinkNode leftroot(TreeLinkNode p){ while(p.next!=null){ if(p.next.left == p)return p.next; else p = p.next; } return null; } }