心血来潮，想实现一下二叉树的四种遍历非递归，就在
发现自己的功夫真的下降，居然用了一个多小时才都在LeetCode上Accept
基本功还需要再练习呀，时间长了不用都快忘了，不过还好理解了这个过程，回忆起来比较快。
其实有个诀窍，就是脑海里模仿一遍动画过程，会记得比较快。
不费话了，上代码：(具体思路和需要注意的地方见注释，以后决定都用英语写注释，剩的乱码，语法不通，请见谅)
先序遍历(栈)
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null) return res;
LinkedList<TreeNode> s = new LinkedList<TreeNode>();
TreeNode p = root;
s.push(root);
while(!s.isEmpty()){
p = s.getFirst();
s.pop();
res.add(p.val);
//because of FILO,must push right node firstly,then push left node .
if(p.right != null) {s.push(p.right);}
if(p.left != null){s.push(p.left);}
}
return res;
}
}
中序遍历(栈)
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root == null) return res;
LinkedList<TreeNode> s = new LinkedList<TreeNode>();
TreeNode p = root;
//Attention:the condition
while(!s.isEmpty()||p!=null){
if(p!=null){
s.push(p);
p = p.left;
}else{
p = s.getFirst();
s.pop();
res.add(p);
p = p.right;
}
}
return res;
}
}
后序遍历(栈)
相对麻烦一下，因为当弹出某个最左节点后，不能直接出其父亲节点，要先去遍历其父亲节点的右子树，所以使用双指针的思想记录之前访问的节点
public class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root==null) return res;
LinkedList<TreeNode> s = new LinkedList<TreeNode>();
//double pointer,p is the current node , q is the pre node
TreeNode p = root;
TreeNode q = new TreeNode(-1);
do{
while(p!=null){//towards left-down
s.push(p);
p = p.left;
}
q = null;
while(!s.isEmpty()){
p = s.getFirst();
s.pop();
//right child is visited or not exist
if(p.right == q){
res.add(p.val);
q = p;//save the node which is visted just now
}else{
//current node does not need vist,push it again
s.push(p);
//deal the right child tree firstly
p = p.right;
break;
}
}
}while(!s.isEmpty());
return res;
}
}
层序遍历(队列)
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
//we use LinkedList as a queue
LinkedList<TreeNode> q = new LinkedList<TreeNode>();
if(root == null) return res;
TreeNode p = root;
q.addLast(p);
while(!q.isEmpty()){
int tmpSize = q.size();
List<Integer> tmpList = new ArrayList<Integer>();
//Attention：i<tmpSize
for(int i=0;i<tmpSize;i++){
p = q.getFirst();
q.poll();
tmpList.add(p.val);
if(p.left!=null) q.addLast(p.left);
if(p.right!=null) q.addLast(p.right);
}
res.add(tmpList);
}
return res;
}
}