脚本宝典收集整理的这篇文章主要介绍了二叉树的三种非递归遍历方式,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
前言: 在之前,我们写到了二叉树的递归 先、中、后序的遍历方式,今天,来讨论这三种遍历方式的非递归实现!!
思路: 类似于层序遍历
代码实现:
public List<Integer> preorderTraversal(Node root) {
List<Integer> result = new ArrayList<>();
// 空树判断
if(root == null){
return result;
}
// 创建一个栈
Stack<Node> stack = new Stack<>();
Node cur = root;
while(!stack.isEmpty() || cur != null){
while(cur != null){
result.add(cur.val);
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
cur = cur.right;
}
return result;
}
思路: 仍然先要创建一个栈,创建一个 cur ,从根节点出发,循环往左找,一直找到 null 为止,路径上遇到的节点都入栈 遇到 null 的时候,就取栈顶元素,并访问(打印) 再让 cur 从当前栈顶元素的右子树出发,循环刚才的过程
代码实现:
public List<Integer> inorderTraversal(Node root) {
//创建一个List
List<Integer> result = new ArrayList<>();
//空树判断
if(root == null){
return result;
}
Stack<Node> stack = new Stack<>();
Node cur = root;
while(!stack.isEmpty() || cur != null){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
result.add(cur.val);
cur = cur.right;
}
return result;
}
思路: 和中序遍历很像 先创建一个栈,创建一个 cur,从根节点出发,循环往左找,一直找到 null 为止,路径上遇到的节点都入栈,(此时还不能访问,若栈顶元素的右子树为 null,或右子树已经被访问过了,才能访问栈顶元素)
右子树是否已经访问:使用一个 prev 记录下后序遍历过程中最后一个被访问到的元素
代码实现:
public List<Integer> postorderTraversal(Node root) {
//创建一个List
List<Integer> result = new ArrayList<>();
//空树判断
if(root == null){
return result;
}
Stack<Node> stack = new Stack<>();
Node cur = root;
Node prev = null;
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if(cur.right == null || cur.right == prev){
result.add(cur.val);
prev = cur;
cur = null;
}
else {
stack.push(cur);
cur = cur.right;
}
}
return result;
}
以上是脚本宝典为你收集整理的二叉树的三种非递归遍历方式全部内容,希望文章能够帮你解决二叉树的三种非递归遍历方式所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。