题目
用非递归版本完成。
程序核心思想
递归版很简单，这里用非递归版本实现了一下。
- 前序遍历
前序遍历需要一个栈。首先压入头结点（为空就返回list），判断如果栈非空，那么出栈一个元素，把这个元素的值加到list中，如果这个节点的右孩子不是null，那么压入右孩子，如果这个节点的左孩子不是null，那么压入左孩子。然后检查栈是不是非空，如此循环。知道栈空了，那么返回list。 - 中序遍历
中序遍历也需要一个栈。中序遍历的循环条件不太一样，是如果栈不是空的或者当前节点不为null，则继续这个循环。这个循环是：如果当前节点不是null，那么当前节点入栈，并且当前节点的指针指向当前节点的左孩子，意思是如果当前节点有左孩子，那么左孩子也入栈，直到当前节点为空。这是出栈一个元素，把这个元素的值加入list，然后当前节点的指针指向出栈元素的右孩子，然后继续这个循环（判断栈非空或者当前节点不为null，当前节点及左孩子入栈...） - 后序遍历
后序遍历是左右中，所以可以把它放到一个栈里面，里面的元素顺序为中右左，这个结构可以对比着前序遍历（中左右）来改，然后该把值存到list中的时候，先存在stack中，等到全部元素进stack之后，在从栈中弹元素，依次进入list，顺序就为左右中了。
Tips
代码
//前序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.util.Stack;
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.empty()){
TreeNode 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;
}
}
//中序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
while(!stack.empty() || root != null){
if(root != null){
stack.push(root);
root = root.left;
}else{
TreeNode cur = stack.pop();
list.add(cur.val);
root = cur.right;
}
}
return list;
}
}
//后序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack1 = new Stack<TreeNode>();
Stack<Integer> stack2 = new Stack<Integer>();
List<Integer> list = new ArrayList<Integer>();
if(root != null){
stack1.push(root);
}else{
return list;
}
while(!stack1.empty()){
TreeNode cur = stack1.pop();
stack2.push(cur.val);
if(cur.left != null) stack1.push(cur.left);
if(cur.right != null) stack1.push(cur.right);
}
while(!stack2.empty()){
list.add(stack2.pop());
}
return list;
}
}
