堆结构

小根堆

前缀树

算法稳定性的坑

二叉树

public static class Node {
    public int value;
    public Node left;
    public Node right;
    public Node(int v) {
        value = v;
    }
}

遍历

递归遍历

public static void f(Node head) {
    if (head == null) {
        return;
    }
    // 先序
    f(head.left);
    // 中序
    f(head.right);
    // 后序
}

非递归遍历

思路：使用栈
先序遍历，顺序为：头左右，则先压入头，弹出头后，有右压右，有左压左

public static void pre(Node head) {
    System.out.print("pre-order: ");
    if (head != null) {
        Stack<Node> stack = new Stack<Node>();
        stack.add(head);
        while (!stack.isEmpty()) {
            head = stack.pop();
            System.out.print(head.value + " ");
            if (head.right != null) {
                stack.push(head.right);
            }
            if (head.left != null) {
                stack.push(head.left);
            }
        }
    }
    System.out.println();
}

后序顺序为：左右头（逆序为头右左），则先压入头，弹出头后，有左压左，有右压右，此时顺序为 头右左 ，是后序遍历的逆序，再准备个栈即可

public static void pos1(Node head) {
    System.out.print("pos-order: ");
    if (head != null) {
        Stack<Node> s1 = new Stack<Node>();
        Stack<Node> s2 = new Stack<Node>();
        s1.push(head);
        while (!s1.isEmpty()) {
            head = s1.pop(); // 头 右 左
            s2.push(head);
            if (head.left != null) {
                s1.push(head.left);
            }
            if (head.right != null) {
                s1.push(head.right);
            }
        }
        // 左 右 头
        while (!s2.isEmpty()) {
            System.out.print(s2.pop().value + " ");
        }
    }
    System.out.println();
}

中序遍历，顺序为：左右头

public static void in(Node cur) {
    System.out.print("in-order: ");
    if (cur != null) {
        Stack<Node> stack = new Stack<Node>();
        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                System.out.print(cur.value + " ");
                cur = cur.right;
            }
        }
    }
    System.out.println();
}

宽度优先遍历

关键点在于如何知道节点所在层

使用map记录节点所在层

在弹出队列时才做操作

public static int maxWidthUseMap(Node head) {
    if (head == null) {
        return 0;
    }
    Queue<Node> queue = new LinkedList<>();
    queue.add(head);
    // key 在 哪一层，value
    HashMap<Node, Integer> levelMap = new HashMap<>();
    levelMap.put(head, 1);
    int curLevel = 1; // 当前你正在统计哪一层的宽度
    int curLevelNodes = 0; // 当前层curLevel层，宽度目前是多少
    int max = 0;
    while (!queue.isEmpty()) {
        // 在弹出队列时才做操作
        Node cur = queue.poll();
        int curNodeLevel = levelMap.get(cur);
        if (cur.left != null) {
            levelMap.put(cur.left, curNodeLevel + 1);
            queue.add(cur.left);
        }
        if (cur.right != null) {
            levelMap.put(cur.right, curNodeLevel + 1);
            queue.add(cur.right);
        }
        if (curNodeLevel == curLevel) {
            curLevelNodes++;
        } else {
            max = Math.max(max, curLevelNodes);
            curLevel++;
            curLevelNodes = 1;
        }
    }
    max = Math.max(max, curLevelNodes);
    return max;
}

记录当前层和下一层的最右节点，就可以知道一层是否已结束

在弹出队列时才做操作

public static int maxWidthNoMap(Node head) {
    if (head == null) {
        return 0;
    }
    Queue<Node> queue = new LinkedList<>();
    queue.add(head);
    Node curEnd = head; // 当前层，最右节点是谁
    Node nextEnd = null; // 下一层，最右节点是谁
    int max = 0;
    int curLevelNodes = 0; // 当前层的节点数
    while (!queue.isEmpty()) {
        // 在弹出队列时才做操作
        Node cur = queue.poll();
        if (cur.left != null) {
            queue.add(cur.left);
            nextEnd = cur.left;
        }
        if (cur.right != null) {
            queue.add(cur.right);
            nextEnd = cur.right;
        }
        curLevelNodes++;
        if (cur == curEnd) {
            max = Math.max(max, curLevelNodes);
            curLevelNodes = 0;
            curEnd = nextEnd;
        }
    }
    return max;
}

二叉树序列化和反序列化

1. 可以用先序、中序、后序序列化或按层遍历，来实现二叉树的变化
2. 用什么方式序列化，就用什么方式反序列化

ps：空的节点也要序列化

递归序列化

// 序列化
public static Queue<String> preSerial(Node head) {
    Queue<String> ans = new LinkedList<>();
    pres(head, ans);
    return ans;
}
public static void pres(Node head, Queue<String> ans) {
    if (head == null) {
        ans.add(null);
    } else {
        // 先序
        ans.add(String.valueOf(head.value));
        pres(head.left, ans);
        // 中序
        pres(head.right, ans);
        // 后序
    }
}
// 反序列化
public static Node buildByPreQueue(Queue<String> prelist) {
    if (prelist == null || prelist.size() == 0) {
        return null;
    }
    return preb(prelist);
}
public static Node preb(Queue<String> prelist) {
    String value = prelist.poll();
    if (value == null) {
        return null;
    }
    // 先序
    Node head = new Node(Integer.valueOf(value));
    head.left = preb(prelist);
    // 中序
    head.right = preb(prelist);
    // 后序
    return head;
}

按层序列化

public static Queue<String> levelSerial(Node head) {
    Queue<String> ans = new LinkedList<>();
    if (head == null) {
        ans.add(null);
    } else {
        ans.add(String.valueOf(head.value));
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(head);
        while (!queue.isEmpty()) {
            head = queue.poll(); // head 父   子
            if (head.left != null) {
                ans.add(String.valueOf(head.left.value));
                queue.add(head.left);
            } else {
                ans.add(null);
            }
            if (head.right != null) {
                ans.add(String.valueOf(head.right.value));
                queue.add(head.right);
            } else {
                ans.add(null);
            }
        }
    }
    return ans;
}
public static Node buildByLevelQueue(Queue<String> levelList) {
    if (levelList == null || levelList.size() == 0) {
        return null;
    }
    Node head = generateNode(levelList.poll());
    Queue<Node> queue = new LinkedList<Node>();
    if (head != null) {
        queue.add(head);
    }
    Node node = null;
    while (!queue.isEmpty()) {
        node = queue.poll();
        node.left = generateNode(levelList.poll());
        node.right = generateNode(levelList.poll());
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
    return head;
}
public static Node generateNode(String val) {
    if (val == null) {
        return null;
    }
    return new Node(Integer.valueOf(val));
}