1.树

1.1 树的存储

以二叉树为例：

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

1.2 树的遍历

1.2.1 前、中、后序遍历

// dfs
public void dfs(TreeNode root) {
    if (root == null) return;
    // 先序
    System.out.println(root.val);
    dfs(root.left);
    // 中序
    // System.out.println(root.val);
    dfs(root.right);
    // 后序
    // System.out.println(root.val);
}

// 非递归先序
public List<Integer> get(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    TreeNode curr = root;
    Deque<TreeNode> q = new LinkedList<>();
    while (curr != null || !q.isEmpty()) {
        if (curr != null) {
            ans.add(curr.val);
            q.offerLast(curr);
            curr = curr.left;
        } else {
            TreeNode tmp = q.pollLast();
            //ans.add(tmp.val);
            curr = tmp.right;
        }
    }
    return ans;
}


// 非递归中序遍历
public List<Integer> get(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    TreeNode curr = root;
    Deque<TreeNode> q = new LinkedList<>();
    while (curr != null || !q.isEmpty()) {
        if (curr != null) {
            q.offerLast(curr);
            curr = curr.left;
        } else {
            TreeNode tmp = q.pollLast();
            ans.add(tmp.val);
            curr = tmp.right;
        }
    }
    return ans;
}

非递归实现树的后序遍历：

public List<Integer> get(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Deque<TreeNode> q = new LinkedList<>();
    // 分别记录当前节点和前一个节点
    TreeNode curr = root, prev = null;
    while (curr != null || !q.isEmpty()) {
        while (curr != null) {
            q.offerLast(curr);
            curr = curr.left;
        } 
        curr = q.peekLast();
        // 当前节点是叶子结点或者该节点的右子树被遍历完了
        if (curr.right == null || curr.right == prev) {
            ans.add(curr.val);
            // 当前节点出栈
            q.pollLast();
            prev = curr;
            curr = null;
        } else {
            // 遍历右子树
            curr = curr.right;
        }
    }
    return ans;
}

1.2.2 层序遍历(BFS)

需要使用一个队列来作为辅助工具来遍历。

public void levelOrder(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            if (node == null) continue;
            // to do
            q.offer(node.left);
            q.offer(node.right);
        }
    }
}

2.图

2.1 图的存储

2.1.1 直接存边

可以使用三元组(start, end, wright)来表示一条从起点start到终点end边的且权重为weight 的一条边。

2.1.2 邻接矩阵

比较适合存储稠密图。

使用一个二维矩阵adj来存储边的信息，如adj[i][j] = w表示点i和j之间存在一条权重为w的边。

int INF = Integer.MAX_VALUE / 2;
int N = 10010;
int[][] adj = new int[N][N];
Arrays.fill(adj, INF); // 初始化
for (Edge edge : edges) {
    int x = edge[0], y = edge[1], w = edge[2];
    adj[x][y] = w;
}

2.1.3 邻接表

比较适合稀疏图。

使用一个支持动态增加元素以及支持索引添加和查找的数据结构来进行存储。如vector<vector<int>>, Map<Integer, Map<Integer, Integer>>, List<List<Integer>>等。

其中，adj[i]保存的是点i所有的出边信息。

HashMap<Integer, HashMap<Integer, Integer>> adj = new HashMap<>();
for (int[] edge : edges) {
    int start = edge[0], end = edge[1], w = edge[2];
    adj.putIfAbsent(start, new HashMap<>());
    adj.get(start).put(end, w);
}

List<List<Integer>> adj = new ArrayList<>();
// 初始化
for (int i = 0; i < n; i++) {
    adj.add(new ArrayList<>());
}
// 添加边信息
for (int[] edge : edges) {
    int from = edge[0], to = edge[1];
    adj.get(from).add(to);
}