JZ8二叉樹的下一個結點
描述
給定一個二叉樹其中的一個結點，請找出中序遍歷順序的下一個結點并且回傳，注意，樹中的結點不僅包含左右子結點，同時包含指向父結點的next指標，
示例:
輸入:{8,6,10,5,7,9,11},8
回傳:9
決議:這個組裝傳入的子樹根節點，其實就是整顆樹，中序遍歷{5,6,7,8,9,10,11}，根節點8的下一個節點就是9，應該回傳{9,10,11}，后臺只列印子樹的下一個節點，所以只會列印9
具體做法：
step 1：首先先根據當前給出的結點找到根節點
step 2：然后根節點呼叫中序遍歷
step 3：將中序遍歷結果存盤下來
step 4：最終拿當前結點匹配是否有符合要求的下一個結點
代碼
package mid.JZ8二叉樹的下一個結點;
import java.util.ArrayList;
class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
public class Solution {
ArrayList<TreeLinkNode> nodes = new ArrayList<>();
public TreeLinkNode GetNext(TreeLinkNode pNode) {
TreeLinkNode root = pNode;
//獲取根節點
while (root.next != null) root = root.next;
//獲取中序遍歷集合
inOrder(root);
//匹配
for (int i = 0; i < nodes.size() - 1; i++) {
if (pNode.val == nodes.get(i).val) {
return nodes.get(i + 1);
}
}
return null;
}
public void inOrder(TreeLinkNode root) {
if (root != null) {
inOrder(root.left);
nodes.add(root);
inOrder(root.right);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/538501.html
標籤：Java
上一篇：二進制列舉（三）