牛客经典笔刷算法题-LC7-非递归求二叉树的前序遍历
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了牛客经典笔刷算法题-LC7-非递归求二叉树的前序遍历，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3187字，纯文字阅读大概需要5分钟。
内容图文
牛客经典笔刷算法题-LC7-非递归求二叉树的前序遍历
------------------------------本题链接---------------------------
题目描述
求给定的二叉树的前序遍历。
备注：用递归来解这道题很简单，你可以给出迭代的解法么？
示例
输入
{1,#,2,3}
返回值
[1,2,3]
思路
上一题我们已经知道了如何递归地进行二叉树遍历
递归确实是一个很好理解的办法，但是调用函数需要做许多工作，比如准备函数内局部变量使用的空间、传递函数的参数等
每次调用函数都需要做这些事情，因此会产生额外开销导致递归效率偏低，所以逻辑上开销一致时递归的额外开销会更多一些
因而，我们有时会考虑用迭代的方法减小递归的开销
我们常常使用栈辅助树的遍历，而对于bfs则用队列辅助计算
这里我们用栈辅助
遍历框架
以下我们来总结一下非递归的遍历框架：
TreeNode设定如下
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
}
先序遍历
public void preorderTraversal (TreeNode root) {
Deque<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode tmp = root;
while(tmp != null||!stack.isEmpty()){
// 根节点存在，则操作根节点，再遍历其左节点和右节点
if(tmp!=null){
// 对根节点的主要操作
func(tmp); // func()为遍历操作
// 根节点入栈
stack.push(tmp);
// 遍历左节点
tmp = tmp.left;
}
// 节点不存在，寻找右节点
else {
tmp = stack.pop();
// 遍历右节点
tmp = tmp.right;
}
}
}
另一种很简单的写法：
public void preorderTraversal (TreeNode root) {
Deque<TreeNode> stack = new LinkedList<TreeNode>(){{ add(root); }};
while(!stack.empty()){
// 根节点出
TreeNode treeroot = stack.pop();
// 操作根节点
func(treeroot)
// 由于是栈，先装入右节点，再装入左节点
// 出栈时，则先遍历左节点，再遍历右节点
if(treeroot.right!=null)
stack.push(treeroot.right);
if(treeroot.left!=null)
stack.push(treeroot.left);
}
}
中序遍历
public void inorderTraversal (TreeNode root) {
Deque<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode tmp = root;
while(tmp!=null||!stack.isEmpty()){
// 迭代寻找左子节点
if(tmp!=null){
// 根节点入栈
stack.push(tmp);
// 遍历左节点
tmp = tmp.left;
}
// 左节点不存在，操作节点寻找右节点
else {
// 遍历根节点
tmp = stack.pop();
// 对节点的主要操作
func(tmp); // func()为遍历操作
// 遍历右节点
tmp = tmp.right;
}
}
}
后序遍历
public void preorderTraversal (TreeNode root) {
Deque<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode tmp = root, pre= root;
while(tmp != null||!stack.isEmpty()){
// 迭代寻找子节点
while(tmp != null){
stack.push(tmp);
tmp = tmp.left;
}
// 左节点不存在，寻找右节点
if(!stack.isEmpty()){
TreeNode treeroot = stack.peek().right;
if(treeroot == null || treeroot == pre){
tmp = stack.pop();
// 对节点的主要操作
func(tmp); // func()为遍历操作
pre=tmp;
tmp=null;
}
else{
tmp = treeroot;
}
}
}
}
有了以上框架，再看二叉树的遍历问题就比较简单了，套入框架就可以解答本题。
解答
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型ArrayList
*/
private ArrayList<Integer> res;
public ArrayList<Integer> preorderTraversal (TreeNode root) {
res = new ArrayList<>();
if(root == null) return res;
Deque<TreeNode> stack = new LinkedList<TreeNode>(){{ add(root); }};
while(!stack.isEmpty()){
TreeNode tmp = stack.pop();
res.add(tmp.val);
if(tmp.right != null) stack.push(tmp.right);
if(tmp.left != null) stack.push(tmp.left);
}
return res;
}
}
内容总结
以上是互联网集市为您收集整理的牛客经典笔刷算法题-LC7-非递归求二叉树的前序遍历全部内容，希望文章能够帮你解决牛客经典笔刷算法题-LC7-非递归求二叉树的前序遍历所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。