算法修炼Day14|递归遍历
LeetCode:二叉树前中后序遍历
1.思路
前中后序的遍历采用递归法,递归三部曲(确定递归函数参数及其返回值、确定终止条件、确定单层递归的顺序)已经内化,happy~
2.代码实现
//前序遍历
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
// 中 - 左 - 右
List<Integer> list = new ArrayList<>();
preorder(root, list);
return list;
}
public void preorder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
list.add(root.val);
preorder(root.left, list);
preorder(root.right, list);
}
}
// 中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
inorder(root, list);
return list;
}
public void inorder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
inorder(root.left, list);
list.add(root.val);
inorder(root.right, list);
}
}
// 后序遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
postorder(root, list);
return list;
}
public void postorder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
postorder(root.left, list);
postorder(root.right, list);
list.add(root.val);
}
}
3.复杂度分析
时间复杂度:(n).
空间复杂度:O(n).
// 层序(前序)遍历,很清晰
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
Stack<TreeNode> stack = new Stack<>();
stack.add(root);
while (!stack.isEmpty()) {
TreeNode temp = stack.pop();
list.add(temp.val);
if (temp.right != null) {
stack.add(temp.right);
}
if (temp.left != null) {
stack.add(temp.left);
}
}
return list;
}
}
// 后序,在前序的基础上反转一下左右节点入栈顺序,目标是左右中,前序是中左右,将前序改为中右左,最后结果即可
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
Stack<TreeNode> stack = new Stack<>();
// 后序:左 -> 右 -> 中
stack.push(root);
while (!stack.isEmpty()) {
TreeNode temp = stack.pop();
list.add(temp.val);
if (temp.left != null) {
stack.push(temp.left);
}
if (temp.right != null) {
stack.push(temp.right);
}
}
Collections.reverse(list);
return list;
}
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgbafhi
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13