94.二叉树的中序遍历
借这个题目延展一下，一次写完前序，后序，中序的递归和非递归写法
一. 递归解法
如下所示，只要调整dfs遍历顺序就可以轻松得到先序，中序，后序的遍历结果了；
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res= new LinkedList<>();
dfs(res,root);
return res;
}
private void dfs(List<Integer> res, TreeNode root) {
if (root==null){
return;
}
dfs(res,root.left);
res.add(root.val);
dfs(res,root.right);
}
}二.非递归解法
1.先序
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res= new LinkedList<>();
Stack<TreeNode> stack=new Stack<>();
if (root==null){
return res;
}
//打印，左，右
stack.push(root);
while (!stack.isEmpty()){
TreeNode curr = stack.pop();
res.add(curr.val);
//栈先进后出，我们要后面打印右树，因此先把右树放进去
if (curr.right!=null){
stack.push(curr.right);
}
if (curr.left!=null){
stack.push(curr.left);
}
}
return res;
}中序
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res= new LinkedList<>();
Stack<TreeNode> stack=new Stack<>();
while (root!=null||stack.size()>0){
//直到不能继续向左再停止
if (root!=null){
stack.add(root);
root=root.left;
//如果root为null说明stack最新的一个结点无左节点，
// 因此直接先打印本节点，再迭代调用B结点
}else {
TreeNode pop = stack.pop();
res.add(pop.val);
root=pop.right;
}
}
return res;
}后序 前面俩我都是用的栈方式，后序遍历我也提供一个栈方式； 后续遍历跟先序遍历比较像,这里是定义了两个栈,把打印的放在打印栈stack2里
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res= new LinkedList<>();
if (root==null){
return res;
}
//先序栈
Stack<TreeNode> stack1=new Stack<>();
//打印栈
Stack<Integer> stack2=new Stack<>();
stack1.push(root);
while (!stack1.isEmpty()){
TreeNode pop = stack1.pop();
stack2.push(pop.val);
if (pop.left!=null){
stack1.push(pop.left);
}
if (pop.right!=null){
stack1.push(pop.right);
}
}
//打印
while (!stack2.isEmpty()){
res.add(stack2.pop());
}
return res;
}跟leetcode学到，这里再提供一个高效的，双向链表版本
{
LinkedList<Integer> res = new LinkedList<>();
if (root == null) {
return res;
}
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || root != null) {
while (root != null) {
res.addFirst(root.val);
stack.push(root);
root = root.right;
}
if (!stack.isEmpty()) {
root = stack.pop();
root = root.left;
}
}
return res;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/10/12 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
