題目描述
給定一個二叉樹和其中的一個結點，請找出中序遍歷順序的下一個結點并且回傳，注意，樹中的結點不僅包含左右子結點，同時包含指向父結點的指標，
思路
若當前結點有右子樹，中序遍歷下一結點為右子樹的最左結點， 若當前結點無右子樹，且是其父結點的左子樹，則中序遍歷下一結點為其父結點， 若當前結點無右子樹，且是其父結點的右子樹，則驗證其父結點的中序遍歷下一結點，時間復雜度O(n)，空間復雜度O(1)，
代碼
/*
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode node) {
if(node == null) return null;
if(node.right != null) {
node = node.right;
while(node.left != null) {
node = node.left;
}
return node;
}
while(node.next != null) {
if(node.next.left == node) {
return node.next;
}
node = node.next;
}
return null;
}
}
筆記
向上驗證父結點無需遞回，while回圈即可，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/79574.html
標籤：其他
上一篇：洗掉鏈表中重復的結點
下一篇：啟發式演算法之遺傳演算法