題目描述
給定一個二叉樹和其中的一個結點，請找出中序遍歷順序的下一個結點并且返回。注意，樹中的結點不僅包含左右子結點，同時包含指向父結點的指針。
算法解析： 如果當前結點的右子節點不為空，那么下一個結點一定出現在當前結點的右子樹上，轉換為尋找當前右子樹中序遍歷的第一個結點。如果當前結點的父節點不為空，且當前結點是父節點的左子節點，則下一個結點一定是父節點，如果當前結點是父節點的右子節點，那么將當前結點和父節點視為一個子樹，直到找到一個父節點，以之為左子樹。
代碼如下：
public TreeLinkNode GetNext(TreeLinkNode pNode) { if (pNode == null){ return null; } TreeLinkNode pNext = null; if (pNode.right != null){ TreeLinkNode PRight = pNode.right; while (pRight.left != null){ pRight = pRight.left; } pNext = pRight; }else if (pNode.next != null){ TreeLinkNode pCurrent = pNode; TreeLinkNode pParent = pNode.next; while (pParent != null && pCurrent == pParent.right){ pCurrent = pParent; pParent = pParent.next; } pNext = pParent; } return pNext; }新聞熱點
疑難解答
