public static void postOrderTraveralWithStack(TreeNode node){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode treeNode = node;
TreeNode lastVisit = null; //标记每次遍历最后一次访问的节点
while(treeNode!=null || !stack.isEmpty()){//节点不为空,结点入栈,并且指向下一个左孩子
while(treeNode!=null){
stack.push(treeNode);
treeNode = treeNode.leftChild;
}
//栈不为空
if(!stack.isEmpty()){
//出栈
treeNode = stack.pop();
/**
* 这块就是判断treeNode是否有右孩子,
* 如果没有输出treeNode.data,让lastVisit指向treeNode,并让treeNode为空
* 如果有右孩子,将当前节点继续入栈,treeNode指向它的右孩子,继续重复循环
*/
if(treeNode.rightChild == null || treeNode.rightChild == lastVisit) {
System.out.print(treeNode.data + " ");
lastVisit = treeNode;
treeNode = null;
}else{
stack.push(treeNode);
treeNode = treeNode.rightChild;
}
}
}
}
全部评论
(0) 回帖