Java二叉树非递归遍历
这里我们用栈的方法遍历树，如果想看递归，和创建树的，见这个博文
非递归我们用stack栈的原则，为先进后出
public static void preOrderTraveralWithStack(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode treeNode = root;
while(treeNode!=null || !stack.isEmpty()){
//迭代访问节点的左孩子，并入栈
while (treeNode != null){
System.out.println(treeNode.data);
stack.push(treeNode);
treeNode = treeNode.leftChild;
}
//如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
if(!stack.isEmpty()){
treeNode = stack.pop();
treeNode = treeNode.rightChild;
}
}
}
我们先向左搜索，往栈里存放，一旦检测到空，则弹出栈顶节点，访问右节点，用右节点替换栈顶节点，一点点遍历，直到栈为空为止。
看图理解一下：
1.首先将节点一放入栈中
2.遍历左节点，放栈中
3，遍历完左边，开始弹出4，用5将2代替。
4.循环以上步骤，直到栈空
下一篇：
简单背包练习——完全背包问题