leetcode 145. 二叉树的后序遍历 迭代和递归
程序员文章站
2024-03-23 09:32:04
...
给定一个二叉树,返回它的 后序 遍历。
- 这种题算经典题了,递归很好写,那么迭代呢,其实也很好写。
public class _145 {
//递归版本 左右根顺序
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans=new ArrayList<>();
dfs(ans,root);
return new ArrayList<>(ans);
}
public void dfs(List<Integer> ans,TreeNode treeNode){
if(treeNode==null){
return;
}
if(treeNode.left!=null){
dfs(ans,treeNode.left);
}
if(treeNode.right!=null){
dfs(ans,treeNode.right);
}
ans.add(treeNode.val);
}
//迭代版本
//迭代的话,就利用栈来模拟,左右根的话 在栈中的顺序就是根右左
public static List<Integer> postorderTraversal1(TreeNode root) {
if(root==null){
return new ArrayList<>();
}
List<Integer> ans=new ArrayList<>();
Stack<TreeNode> stack=new Stack<>();
stack.add(root);
while (!stack.isEmpty()){
TreeNode cur=stack.pop();
if(cur.left==null&&cur.right==null){ //左右结点都为空则添加到list中
ans.add(cur.val);
continue;
}
stack.push(new TreeNode(cur.val));//直接添加新的结点 新建TreeNode
if(cur.right!=null){ //添加右边
stack.push(cur.right);
}
if(cur.left!=null) { //添加左边
stack.push(cur.left);
}
}
return ans;
}
}
推荐阅读
-
leetcode 145. 二叉树的后序遍历 迭代和递归
-
二叉树三种遍历方式的递归和非递归写法(python 实现)
-
java实现二叉树前序、中序、后序递归遍历详解步骤和图解
-
二叉树遍历的递归、非递归方法(前序、中序、后序,层序)——Java实现
-
已知二叉树的中序遍历序列和后序遍历序列,求前序遍历序列
-
二叉树的前序,中序,后序非递归遍历(C&C++)
-
【LeetCode】104. Maximum Depth of Binary Tree 二叉树的深度 DFS BFS 递归方式 迭代方式 JAVA
-
145. 二叉树的后序遍历
-
145. 二叉树的后序遍历
-
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例