定义树的节点如下
public class TreeNode {
public Integer data;
public TreeNode leftChild;
public TreeNode rightChild;
}
非递归前序遍历
方法一
考虑一般情况，对于给定的一个节点，可以按下面三个步骤遍历：
1、持续遍历左子节点，直到左子节点为空。
2、弹出栈顶元素，访问它的右子节点。
3、继续第一步，直到栈空。
public List<TreeNode> preOrder(TreeNode root) {
List<TreeNode> result = new ArrayList<>();
if (root == null) {
return result;
}
TreeNode cur = root;
Deque<TreeNode> stack = new LinkedList<>();
while (cur != null || !stack.isEmpty()) {
// 持续遍历左子树，直到左子树为空
while (cur != null) {
result.add(cur);
stack.push(cur);
cur = cur.leftChild;
}
if (!stack.isEmpty()) {
cur = stack.pop();
cur = cur.rightChild;
}
}
return result;
}
方法二
根据栈的弹出顺序来遍历，考虑下面三个步骤
1、利用给定的节点初始化栈，保证栈不为空。
2、访问栈顶元素，然后将其右子节点、左子节点分别入栈。
3、重复步骤2，直到栈为空。
public List<TreeNode> preOrder(TreeNode root) {
List<TreeNode> result = new ArrayList<>();
if (root == null) {
return result;
}
TreeNode cur = root;
Deque<TreeNode> stack = new LinkedList<>();
// 首先跟节点入栈，保证栈不为空
stack.push(cur);
while (!stack.isEmpty()) {
// 访问栈顶元素
cur = stack.pop();
result.add(cur);
// 右子节点、左子节点分别入栈
if (cur.rightChild != null) {
stack.push(cur.rightChild);
}
if (cur.leftChild != null) {
stack.push(cur.leftChild);
}
}
return result;
}
非递归中序遍历
这里采用的方法与前序遍历中介绍的第一种方法类似：
1、持续遍历左子节点，只入栈不访问，直到左子节点为空。
2、弹出栈顶元素，这个时候访问该节点，访问它的右子节点。
3、继续第一步，直到栈空。
public List<TreeNode> inOrder(TreeNode root) {
List<TreeNode> result = new ArrayList<>();
if (root == null) {
return result;
}
TreeNode cur = root;
Deque<TreeNode> stack = new ArrayDeque<>();
while (cur != null || !stack.isEmpty()) {
// 只入栈，不访问
while (cur != null) {
stack.push(cur);
cur = cur.leftChild;
}
// 出栈的时候访问
if (!stack.isEmpty()) {
cur = stack.pop();
result.add(cur);
cur = cur.rightChild;
}
}
return result;
}
非递归后序遍历
非递归遍历被称为三种遍历中最难的一个，这里，我们分别用三种方法来实现
方法一
后序遍历可以看做是从右到左的先序遍历的逆过程，所以可以利用辅助栈，按照从右至左的先序遍历，遍历的结果存到辅助栈里，然后将辅助栈的元素依次出栈。
public List<TreeNode> postOrder(TreeNode root) {
List<TreeNode> result = new ArrayList<>();
if (root == null) {
return result;
}
TreeNode cur = root;
// 辅助栈
Deque<TreeNode> assistStack = new ArrayDeque<>();
// 用于保存从右到左先序遍历节点的栈
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(cur);
while (!stack.isEmpty()) {
cur = stack.pop();
assistStack.push(cur);
if (cur.leftChild != null) {
stack.push(cur.leftChild);
}
if (cur.rightChild != null) {
stack.push(cur.rightChild);
}
}
// 将辅助栈元素依次出栈
while (!assistStack.isEmpty()) {
cur = assistStack.pop();
result.add(cur);
}
return result;
}
方法二
对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点。
此时该结点出现在栈顶，但是此时不能将其出栈并访问，因为其右孩子还未被访问。所以，接下来按照相同的规则对其右子树进行相同的处理。当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。
在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。
public List<TreeNode> postOrder3() {
List<TreeNode> result = new ArrayList<>();
if (root == null) {
return result;
}
// 用来保存当前节点是第几次访问
Map<TreeNode, Integer> visitedNodes = new HashMap<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
visitedNodes.put(cur, 1);
stack.push(cur);
cur = cur.leftChild;
}
if (!stack.isEmpty()) {
cur = stack.pop();
int visitCount = visitedNodes.getOrDefault(cur, 0);
// 第二次出现在栈顶才访问
if (visitCount < 2) {
visitedNodes.put(cur, visitCount + 1);
stack.push(cur);
cur = cur.rightChild;
} else {
result.add(cur);
cur = null;
}
}
}
return result;
}
方法三
根据后续遍历的访问情况，我们可以总结出一般规律，对于任一结点P，有且只有两种情况下才可以对其访问：
1、如果P不存在左孩子和右孩子，则可以直接访问它；
2、P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。
若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
public List<TreeNode> postOrder4() {
List<TreeNode> result = new ArrayList<>();
if (root == null) {
return result;
}
TreeNode cur = root;
// 保存上一个访问的节点，
// 用来判断上一个访问的节点是不是当前节点的左子节点或右子节点
TreeNode pre = null;
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(cur);
while (!stack.isEmpty()) {
cur = stack.peek();
// 1）叶子节点直接访问
// 2）如果当前节点要被加到result中，则一定满足：
// 1、左子节点刚刚被添加（没有右子节点的情况）
// 2、右子节点刚刚被添加（有或没有左子节点）
if ((cur.leftChild == null && cur.rightChild == null) ||
(pre != null && (pre == cur.leftChild || pre == cur.rightChild))) {
result.add(cur);
stack.pop();
pre = cur;
} else {
if (cur.rightChild != null) {
stack.push(cur.rightChild);
}
if (cur.leftChild != null) {
stack.push(cur.leftChild);
}
}
}
return result;
}
完！
网友评论