給定一個二叉樹和其中的一個結點，請找出中序遍歷順序的下一個結點并且回傳，注意，樹中的結點不僅包含左右子結點，同時包含指向父結點的指標
解題思路
中序遍歷的順序是先左子結點（左子樹），再自己，最后才是右子結點（右子樹），現在題目的要求是給定一個二叉樹中的某一結點，求其在中序遍歷順序的下一個結點，因此根據中序遍歷的性質我們不難推斷：
- 目標結點有右子樹，那么它的下一個結點就是右子樹最左邊的結點
- 目標結點沒有右子樹，也可以分成兩類：
- 目標結點是其父結點左孩子，那么父節點就是下一個結點
- 目標結點是其父結點右孩子，找它的父結點的父結點的父結點，直到當前結點是其父結點的左孩子位置，如果沒找到，說明當前結點已經是尾結點
public class Solution {
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;
}
// 到了根節點仍沒找到，則回傳 null
return null;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/236432.html
標籤：其他
上一篇：洗掉鏈表中重復的結點