LeetCode 144： 二叉树的前序遍历
📖 解题思路：
（1）二叉树的前序遍历：
重复子问题： 根结点 左子树 右子树
递归结束条件： 当前结点为空
（2）此题需要一个List集合来维护遍历过的结点的值
- ArrayList 与 LinkedList 的区别：
两者都实现了List的接口，前者的底层是数组，后者的底层是链表
前者便于查找，时间复杂度为O(1);后者便于添加和删除，但后者需要更多的存储空间
📝 Java递归版本:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
//设计一个方法，来完成前序遍历与结点值的记录
public void preorder(TreeNode root, ArrayList res){
//如果当前结果为空，那么直接返回空
if(root == null){
return;
}
res.add(root.val);
//递归左子树
preorder(root.left, res);
//递归右子树
preorder(root.right, res);
}
public List<Integer> preorderTraversal(TreeNode root) {
/**
前序遍历属于自顶向下的遍历，递归部分：根结点 左子树 右子树
递归结束条件：当前结点值为空
返回值为一个集合，也就是要将结点的元素值添加到集合中
输出错误分析：
因为我采用的是递归遍历二叉树，但是没有把递归的算法分离出来，
这样在没次进入新结点时，都会创建一个新的集合，这样就导致集
合中只保存了一个值
PS:
（1）ArrayList与LinkedList的区别：
两者都实现类List接口，但是前者的底层实现原理是数组，
后者的实现原理是链表；
前者查询速度更快，后者插入删除操作更快；
后者每个结点存储两个引用，所以后者更占空间
*/
//创建一个结合
ArrayList<Integer> res = new ArrayList<Integer>();
preorder(root, res);
return res;
}
}
📝 Java迭代版本:
LeetCode 94: 二叉树的中序遍历
?? 解题思路：
大体部分与前序遍历类似，再添加元素到集合中时，先遍历左子树再添加元素即可
? Java递归版本:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
//定义一个方法来完成中序遍历
public void inorder(TreeNode root, ArrayList res){
if(root == null){
return;
}
//递归左子树
inorder(root.left, res);
//将结点值添加到集合中
res.add(root.val);
//递归右子树
inorder(root.right, res);
}
public List<Integer> inorderTraversal(TreeNode root) {
//创建一个集合
ArrayList<Integer> res = new ArrayList<Integer>();
//调用中序遍历的方法
inorder(root, res);
return res;
}
}
LeetCode 145: 二叉树的后序遍历
🅰? 解题思路:
与前序和中序类似，最后处理根结点
🅱? Java递归版本:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public void postorder(TreeNode root, ArrayList res){
if(root == null){
return;
}
postorder(root.left,res);
postorder(root.right, res);
res.add(root.val);
}
public List<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<Integer>();
postorder(root, res);
return res;
}
}
