理论基础
需要了解 二叉树的种类，存储方式，遍历方式 以及二叉树的定义
文章讲解
| 类型 | 实现类 | 底层实现 | 插入时间复杂度 | 删除时间复杂度 | 查找时间复杂度 |
|---|---|---|---|---|---|
| Map | HashMap | 哈希表 (Hash Table) | (O(1)) 平均 | (O(1)) 平均 | (O(1)) 平均 |
| LinkedHashMap | 哈希表 + 双向链表 | (O(1)) 平均 | (O(1)) 平均 | (O(1)) 平均 | |
| TreeMap | 红黑树 (Red-Black Tree) | (O(\log n)) | (O(\log n)) | (O(\log n)) | |
| ConcurrentHashMap | 分段锁的哈希表 (Segmented Hash Table) | (O(1)) 平均 | (O(1)) 平均 | (O(1)) 平均 | |
| EnumMap | 数组 (Array) | (O(1)) | (O(1)) | (O(1)) | |
| IdentityHashMap | 哈希表 (基于对象引用) | (O(1)) 平均 | (O(1)) 平均 | (O(1)) 平均 | |
| Set | HashSet | 哈希表 (Hash Table) | (O(1)) 平均 | (O(1)) 平均 | (O(1)) 平均 |
| LinkedHashSet | 哈希表 + 双向链表 | (O(1)) 平均 | (O(1)) 平均 | (O(1)) 平均 | |
| TreeSet | 红黑树 (Red-Black Tree) | (O(\log n)) | (O(\log n)) | (O(\log n)) |
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;
}
}
递归遍历 （必须掌握）
/**
* 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;
* }
* }
*/
//LC144
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
preOrder(root, res);
return res;
}
private void preOrder(TreeNode root, List<Integer> res){
if(root == null){
return ;
}
res.add(root.val);
preOrder(root.left, res);
preOrder(root.right, res);
}
}
//LC94 inorder
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inOrder(root, res);
return res;
}
private void inOrder(TreeNode root, List<Integer> res){
if(root == null){
return ;
}
inOrder(root.left, res);
res.add(root.val);
inOrder(root.right, res);
}
}
//LC145 postorder
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
postOrder(root, res);
return res;
}
private void postOrder(TreeNode root, List<Integer> res){
if(root == null){
return;
}
postOrder(root.left, res);
postOrder(root.right, res);
res.add(root.val);
}
}
迭代遍历 （基础不好的录友，迭代法可以放过）
迭代的过程
1.处理：将元素放进result数组中
2.访问：遍历节点前序遍历
因为出栈顺序是：中左右。先访问的元素是中间节点，要处理的元素也是中间节点
所以压栈顺序是：中右左中序遍历
使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。后序遍历
顺序 左-右-中
入栈顺序：中-左-右
出栈顺序：中-右-左， 最后翻转结果
代码暂时先不写了，有时间再来练
统一迭代 （基础不好的录友，迭代法可以放过）
标记法：将访问的节点放入栈中，把要处理的节点也放入栈，紧接着放入一个空指针作为标记。
层序遍历
思路
- 借助队列保存每一层终端额元素
- 根节点入队，记录size。
- 记录当前层的大小，把元素弹出来
- 把下一层的左孩子，右孩子加入队列，遍历后把这一层的元素弹出来（弹出的数量记录了下来，只弹出这一层记录的数量）
代码实现
/**
* 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 List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(root != null) queue.add(root);
while(!queue.isEmpty()){
int size = queue.size(); //当前层节点的个数
List<Integer> level = new ArrayList<>(); //用来放这一层节点
//遍历队列
for(int i = 0; i < size; i++){
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
result.add(level);
}
return result;
}
}
