文章目录
- 二叉树的存储方式
- 二叉树的遍历方式
- DFS--递归遍历
- DFS--迭代遍历
- BFS--层次遍历 LC102
二叉树的存储方式
链式存储（指针）或 顺序存储（数组）
(1)链式存储：通过指针把分布在各个地址的节点串联一起。
(2)顺序存储：元素在内存是连续分布的，就是用数组来存储二叉树。
遍历方式：如果父节点的数组下标是 i，那么它的左孩子就是 2i + 1，右孩子 2i + 2，孩子的父节点为（i-1）/2。
链式存储的二叉树节点的定义方式（二叉树的定义和链表是差不多的，相对于链表 ，二叉树的节点里多了一个指针， 有两个指针，指向左右孩子）
public class TreeNode {
int val;
TreeNode left; //表示左子节点的引用，类型为TreeNode
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;
}
}
二叉树的遍历方式
-
广度优先遍历
- 层次遍历（迭代法）
-
深度优先遍历
- 前序遍历（递归法，迭代法）
- 中序遍历（递归法，迭代法）
- 后序遍历（递归法，迭代法）
DFS–递归遍历
// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
preorder(root, result);
return result;
}
public void preorder(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
result.add(root.val);
preorder(root.left, result);
preorder(root.right, result);
}
public void preorder(TreeNode root, List<Integer> result) {
// if (root != null) {
// result.add(root.val);
// preorder(root.left, result);
// preorder(root.right, result);
// }
// }
}
// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inorder(root, res);
return res;
}
void inorder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
inorder(root.left, list);
list.add(root.val);
inorder(root.right, list);
}
}
// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
postorder(root, res);
return res;
}
void postorder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
postorder(root.left, list);
postorder(root.right, list);
list.add(root.val);
}
}
DFS–迭代遍历
// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
//必须要先判断，因为如果root==null，在执行 stack.push(root)时将会抛出空指针异常
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if (node.right != null){
stack.push(node.right);
}
if (node.left != null){
stack.push(node.left);
}
}
return result;
}
}
// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
//stack.push(root);(不能先把根节点入栈)
while(cur != null || !stack.isEmpty()){
// 尽可能深入左子树
if(cur != null){
stack.push(cur);
cur = cur.left;
}
//当前节点为空，说明左子树已经遍历完毕，弹出栈顶元素,再处理右子树
else{
cur = stack.pop();
result.add(cur.val);
cur = cur.right;
}
}
return result;
}
}
// 后序遍历：先序遍历是中左右，我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if (node.left != null){
stack.push(node.left);
}
if (node.right != null){
stack.push(node.right);
}
}
Collections.reverse(result);
return result;
}
}
BFS–层次遍历 LC102
//BFS--迭代方式--借助队列 （题源）
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> resList = new ArrayList<>();
if (root == null) {
return resList;
}
//创建一个队列，使用 LinkedList 作为底层实现
Queue<TreeNode> que = new LinkedList<>();
que.offer(root); //将元素插入到队尾
while(!que.isEmpty()){
List<Integer> itemList = new ArrayList<>();
int levelSize = que.size();
//for(int i = 0;i < que.size();i++) 不正确，因为for循环过程中size会变化
for (int i = 0; i < levelSize; i++) {
//移除并返回队列头部的元素,如果队列为空，则返回null
TreeNode tmpNode = que.poll();
itemList.add(tmpNode.val);
if(tmpNode.left != null){
que.offer(tmpNode.left);
}
if(tmpNode.right != null){
que.offer(tmpNode.right);
}
}
resList.add(itemList);
}
return resList;
}
}
//BFS--递归方式
class Solution {
List<List<Integer>> resList = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
// 初始层级为0，调用递归函数处理
checkFun01(root, 0);
return resList;
}
public void checkFun01(TreeNode node, int deep) {
if (node == null) {
return;
}
deep++;
//当层级增加时，确保resList中已经有足够的层级列表
if (resList.size() < deep) {
resList.add(new ArrayList<Integer>());
}
// 将当前节点值加入对应层级的列表中
resList.get(deep - 1).add(node.val);
// 递归处理左右子节点
checkFun01(node.left, deep);
checkFun01(node.right, deep);
}
}
LC107自底向上的层序遍历，就是在最后将集合翻转即可：Collections.reverse(resList);
