在Java中,優化TreeNode的遍歷可以通過以下幾種方法實現:
import java.util.LinkedList;
import java.util.Queue;
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public void inorderTraversal(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode currentNode = queue.poll();
// 處理當前節點
System.out.print(currentNode.val + " ");
// 將右子節點和左子節點按順序加入隊列
if (currentNode.right != null) {
queue.offer(currentNode.right);
}
if (currentNode.left != null) {
queue.offer(currentNode.left);
}
}
}
public void morrisTraversal(TreeNode root) {
TreeNode currentNode = root;
while (currentNode != null) {
if (currentNode.left == null) {
// 處理當前節點
System.out.print(currentNode.val + " ");
currentNode = currentNode.right;
} else {
// 找到當前節點左子樹的最右節點
TreeNode predecessor = currentNode.left;
while (predecessor.right != null && predecessor.right != currentNode) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
// 將當前節點左子樹的最右節點的右指針指向當前節點
predecessor.right = currentNode;
currentNode = currentNode.left;
} else {
// 恢復樹的結構并移動到右子樹
predecessor.right = null;
// 處理當前節點
System.out.print(currentNode.val + " ");
currentNode = currentNode.right;
}
}
}
}
import java.util.List;
import java.util.stream.Collectors;
public List<TreeNode> trees = // ... 初始化多個樹結構
trees.parallelStream().forEach(this::inorderTraversal);
通過以上方法,可以根據具體的應用場景和需求選擇合適的優化策略,以提高TreeNode的遍歷效率。