使用非递归的方式,实现一个二又树的后序遍历。 Java代码实现
时间: 2024-09-26 09:05:37 浏览: 16
非递归方式实现二叉树的后序遍历通常会使用栈的数据结构。以下是Java代码的一个实现:
```java
import java.util.Stack;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class PostorderTraversalNonRecursive {
public List<Integer> postorderTraversal(TreeNode root) {
if (root == null) return new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
boolean isLeft = true; // 标记当前访问的是左孩子还是右孩子
List<Integer> result = new ArrayList<>();
TreeNode current = root;
while (!stack.isEmpty() || current != null) {
while (current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop(); // 弹出最右边的节点
if (isLeft) {
result.add(current.val); // 左孩子先输出
isLeft = false;
} else {
isLeft = true; // 切换到右孩子
current = current.right;
}
}
return result;
}
}
```
在这个代码中,我们首先将所有左子节点压入栈中,然后每次从栈顶弹出节点并将其值添加到结果列表中,同时切换到下一个未访问的孩子节点(左孩子变为右孩子,反之亦然)。这样就能保证按照后序遍历的顺序(右->左->根)处理每个节点。