原题描述
分别使用递归、非递归方法，实现二叉树的先序、中序和后序遍历。
解题思路
使用递归方法实现二叉树的遍历，简单至极，此处不再赘述。 对于非递归方法，可以采用栈这种“先进后出”的数据结构，然后根据不同遍历方法的特点，画图分析其入栈、出栈的时机，最后将其转化成代码实现。三种遍历方法的实现流程如下：
先序遍历
- 根结点入栈；
- 对于任一栈顶结点P，访问P并将其出栈；
- 若P有右结点，则将P的右结点入栈；若P有左结点，则将P的左结点入栈；
- 循环跳转到步骤2，直到栈为空。
中序遍历
- 当前结点初始化为根结点；
- 对于任一当前结点P：若P有左结点，则将P入栈，并将当前结点置为P的左结点；否则访问栈顶结点将其出栈，并将当前结点置为P的右结点；
- 循环跳转到步骤2，直到栈为空或者当前结点为空。
后序遍历
后序遍历的关键点，是要保证根结点必须要其孩子结点之后被访问，因此当一个结点要出栈时，该结点要么是叶子结点，要么前一个出栈的结点为该结点的孩子结点。这就需要额外维护一个结点pre，用来记录前一个出栈的结点。具体流程如下：
- 根结点入栈；
- 对于任一栈顶结点P，若P为叶子结点或者前一个出栈结点为该结点的孩子结点，则访问P并将其出栈，同时将P设置为前一个结点pre，供下次要出栈的结点参考（比较pre是否为下次出栈结点的孩子结点）；否则，依次将P的右结点和左结点入栈。
- 循环跳转到步骤2，直到栈为空。
实现代码
public class Solution {
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int x) {
val = x;
}
}
// 先序遍历--递归实现
public List<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
if (root == null) {
return list;
}
list.add(root.val);
list.addAll(preorderTraversal(root.left));
list.addAll(preorderTraversal(root.right));
return list;
}
// 中序遍历--递归实现
public List<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
if (root == null) {
return list;
}
list.addAll(inorderTraversal(root.left));
list.add(root.val);
list.addAll(inorderTraversal(root.right));
return list;
}
// 后序遍历--递归实现
public List<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
if (root == null) {
return list;
}
list.addAll(postorderTraversal(root.left));
list.addAll(postorderTraversal(root.right));
list.add(root.val);
return list;
}
// 先序遍历--非递归实现
public List<Integer> preorderStack(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
if (root == null)
return list;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
TreeNode cur = null;
while (!stack.empty()) {
cur = stack.pop();
list.add(cur.val);
//先压入右结点，在压入左结点--栈的"先进后出"特性
if (cur.right != null)
stack.push(cur.right);
if (cur.left != null)
stack.push(cur.left);
}
return list;
}
// 中序遍历--非递归实现
public List<Integer> inorderStack(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
if (root == null)
return list;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while (!stack.empty() || cur != null) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
TreeNode temp = stack.pop();
list.add(temp.val);
cur = temp.right;
}
}
return list;
}
// 后序遍历--非递归实现
public List<Integer> postorderStack(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
if (root == null)
return list;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
TreeNode pre = null;
while (!stack.empty()) {
TreeNode cur = stack.peek();
if ((cur.left == null && cur.right == null) ||
(pre != null && (pre == cur.left || pre == cur.right))) {
list.add(cur.val);
stack.pop();
pre = cur;
}else {
if (cur.right != null)
stack.push(cur.right);
if (cur.left != null)
stack.push(cur.left);
}
}
return list;
}
}
