[模版总结] - 树的基本算法1

树结构定义

一种非线性存储结构，具有存储“一对多”关系的数据元素集合

种类

General Tree
- Trie
- B/B+ 树
二叉树
- 满/完满/完全二叉树
  - 完美BT : 除了叶子结点外所有节点都有两个字节点，每一层都完满填充
  - 完全BT：除最后一层以外其他每一层都完美填充，最后一层从左到右紧密填充
  - 完满BT: 除了叶子结点外所有节点都有两个字节点
- 二叉搜索树 BST
  - 平衡BST
    - 红黑树
    - 伸展树
    - 自平衡二叉查找树AVL
    - 替罪羊树
- 线索二叉树
- 霍夫曼树/最优二叉树

二叉树遍历方式

所有二叉树基本遍历时间复杂度均为： $O(N)$ , 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

递归写法

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);}
}

一些特别的遍历：

逐列遍历

$T: O(N + C\times RlogR)$ , 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);}
}