首页 > 给定一个二叉树,返回该二叉树层序遍历的结果
头像
牛客60793768号
编辑于 2021-06-09 09:05
+ 关注

给定一个二叉树,返回该二叉树层序遍历的结果

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) 回帖
加载中...
话题 回帖

相关热帖

近期精华帖

热门推荐