二叉树的定义 以及前中后序,层序遍历
程序员文章站
2022-06-28 16:21:27
class Solution { List list = new ArrayList<>(); public List preorderTraversal(TreeNode root) { if(root==null) return new ArrayList<>(); list.add(root.val); preorderTra.....
class Solution {
List <Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root==null)
return new ArrayList<>();
list.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
return list;
}
}
class Solution {
List <Integer> list = new ArrayList<Integer>();
public List<Integer> inorderTraversal(TreeNode root) {
if(root == null)
return list;
inorderTraversal(root.left);
list.add(root.val);
inorderTraversal(root.right);
return list;
}
}
class Solution {
List <Integer> list = new ArrayList<Integer>();
public List<Integer> postorderTraversal(TreeNode root) {
if(root == null)
return new ArrayList<Integer>();
postorderTraversal(root.left);
postorderTraversal(root.right);
list.add(root.val);
return list;
}
}
层序遍历:
层序遍历我认为也可以看作是树的广度优先搜索(BFS),以根节点开始,依次遍历一级邻接点,二级邻接点…等等
具体实现是用队列去实现
力扣对于层序遍历的演示
class Solution {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> list = new ArrayList<List<Integer>>();
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null)
return list;
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> innerList = new ArrayList<Integer>();;
while(size--!=0){
TreeNode treeNode = queue.poll();
innerList.add(treeNode.val);
if(treeNode.left != null)
queue.add(treeNode.left);
if(treeNode.right != null)
queue.add(treeNode.right);
}
if(innerList != null)
list.add(innerList);
}
return list;
}
}
本文地址:https://blog.csdn.net/m0_45311187/article/details/110815326
上一篇: 腌制肉要放冰箱吗
下一篇: 2021-01-05
推荐阅读
-
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
-
【算法】二叉树的前序、中序、后序、层序遍历和还原。
-
Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】
-
L2-006 树的遍历 (后序中序求层序)
-
已知后序遍历和中序遍历求层序遍历(树的遍历)
-
数据结构---树的前、中、后序遍历递归实现以及层次遍历实现
-
剑指 Offer 07. 重建二叉树——【前中序】和【中后序】重建二叉树的递归思路详解
-
二叉树的先序遍历、中序遍历、后序遍历
-
【LeetCode】二叉树各种遍历大汇总(秒杀前序、中序、后序、层序)递归 & 迭代
-
JavaScript实现二叉树的先序、中序及后序遍历方法详解