树结构定义
一种非线性存储结构，具有存储“一对多”关系的数据元素集合
种类
- General Tree
- Trie
- B/B+ 树
- 二叉树
- 满/完满/完全二叉树
- 完美BT : 除了叶子结点外所有节点都有两个字节点，每一层都完满填充
- 完全BT： 除最后一层以外其他每一层都完美填充，最后一层从左到右紧密填充
- 完满BT: 除了叶子结点外所有节点都有两个字节点
- 二叉搜索树 BST
- 平衡BST
- 红黑树
- 伸展树
- 自平衡二叉查找树AVL
- 替罪羊树
- 平衡BST
- 线索二叉树
- 霍夫曼树/最优二叉树
- 满/完满/完全二叉树
二叉树遍历方式
所有二叉树基本遍历时间复杂度均为：, N代表结点数量。
前序遍历 (根左右)
- 题目：Leetcode 144
递归写法
由于前序的特性，他可以展示树结构的继承关系，所以通常前序遍历会用在复制/打印树结构，比如序列化/反序列化，打印文件系统结构。
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
dc(root, res);
return res;
}
private void dc(TreeNode root, List<Integer> res) {
if (root==null) return;
res.add(root.val);
dc(root.left, res);
dc(root.right, res);
}
}中序遍历 (左根右)
- 题目：Leetcode 94
递归写法
中序遍历最常用就是打印BST结构
class Solution {
List<Integer> res;
public List<Integer> inorderTraversal(TreeNode root) {
res = new ArrayList<>();
dc(root);
return res;
}
private void dc(TreeNode root) {
if (root==null) return;
dc(root.left);
res.add(root.val);
dc(root.right);
}
}后续遍历 (左右根)
- 题目：Leetcode 145
后续遍历由于特性是先搜索叶子结点，所以可以用来做一些叶子结点操作(删除叶子结点)，还有一些归并操作(计算算术表达式)
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
dc(root, res);
return res;
}
private void dc(TreeNode root, List<Integer> res) {
if (root==null) return;
dc(root.left, res);
dc(root.right, res);
res.add(root.val);
}
}层级遍历 I - 自上而下
- 题目：Leetcode 102
树/图类层级遍历直接BFS即可
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root==null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> tmp = new ArrayList<>();
for (int i=0; i<size; i++) {
TreeNode curr = q.poll();
tmp.add(curr.val);
if (curr.left!=null) q.add(curr.left);
if (curr.right!=null) q.add(curr.right);
}
res.add(tmp);
}
return res;
}
}层级遍历 II - 自下而上
- 题目：Leetcode 107
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root==null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> tmp = new ArrayList<>();
for (int i=0; i<size; i++) {
TreeNode curr = q.poll();
if (curr.left!=null) q.add(curr.left);
if (curr.right!=null) q.add(curr.right);
tmp.add(curr.val);
}
res.add(0, tmp);
}
return res;
}
}ZigZag 遍历
- 题目：Leetcode 103
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
dfs(root, 0, res);
return res;
}
private void dfs(TreeNode root, int height, List<List<Integer>> res) {
if (root==null) return;
if (res.size()<=height) res.add(new ArrayList<>());
if (height%2==0) {
res.get(height).add(root.val);
} else {
res.get(height).add(0, root.val);
}
dfs(root.left, height+1, res);
dfs(root.right, height+1, res);
}
}一些特别的遍历：
逐列遍历
, N表示dfs遍历时间复杂度，C表示列数，R表示每一列的行数
- 题目：Leetcode 314
class Solution {
TreeMap<Integer, List<Pair<Integer, Integer>>> colMap;
public List<List<Integer>> verticalOrder(TreeNode root) {
if (root==null) return new ArrayList<>();
colMap = new TreeMap<>();
dfs(root, 0, 0);
List<List<Integer>> res = new ArrayList<>();
for (int idx: colMap.keySet()) {
Collections.sort(colMap.get(idx), (a, b) -> {
return a.getKey()-b.getKey();
});
List<Integer> tmp = new ArrayList<>();
for (Pair<Integer, Integer> a: colMap.get(idx)) {
tmp.add(a.getValue());
}
res.add(tmp);
}
return res;
}
private void dfs(TreeNode root, int row, int col) {
if (root==null) return;
colMap.putIfAbsent(col, new ArrayList<>());
colMap.get(col).add(new Pair<>(row, root.val));
dfs(root.left, row+1, col-1);
dfs(root.right, row+1, col+1);
}
}
