二叉树的存储方式和遍历方式
文章目录
- 二叉树的存储方式
- 二叉树的遍历方式
- DFS--递归遍历
- DFS--迭代遍历
- BFS--层次遍历 LC102
二叉树的存储方式
链式存储(指针)或 顺序存储(数组)
(1)链式存储:通过指针把分布在各个地址的节点串联一起。
(2)顺序存储:元素在内存是连续分布的,就是用数组来存储二叉树。
遍历方式:如果父节点的数组下标是 i,那么它的左孩子就是 2i + 1,右孩子 2i + 2,孩子的父节点为(i-1)/2。
链式存储的二叉树节点的定义方式(二叉树的定义和链表是差不多的,相对于链表 ,二叉树的节点里多了一个指针, 有两个指针,指向左右孩子)
public class TreeNode {int val;TreeNode left; //表示左子节点的引用,类型为TreeNodeTreeNode 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++) {//移除并返回队列头部的元素,如果队列为空,则返回nullTreeNode 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);