算法 | 第4章 树与图相关《程序员面试金典》

2021-10-25  本文已影响0人  多氯环己烷

前言

本系列笔记主要记录笔者刷《程序员面试金典》算法的一些想法与经验总结，按专题分类，主要由两部分构成：经验值点和经典题目。其中重点放在经典题目上；

本章有10题，标号到12，没有第7和第11题；

0. *经验总结

0.1 程序员面试金典 P85

0.2 各种树的特点

1. 二叉搜索树（二叉排序树）

二叉搜索树

2. 平衡二叉树

3. 完整二叉树

完整二叉树

4. 满二叉树

满二叉树

5. 完满二叉树

完满二叉树

6. 二叉堆（小顶堆和大顶堆）

二叉堆（小顶堆和大顶堆）

7. 单次查找树（前序树）

单次查找树（前序树）

8. 顺序存储二叉树

顺序存储二叉树

9. 线索化二叉树

线索化二叉树

10. 霍夫曼树

霍夫曼树

11. B树、B+树和B*树

B树
B+树
B*树

0.3 树的三种遍历方式

中序遍历：

void inOrderTraversal(TreeNode node){
    if(node != null){
        inOrderTraversal(node.left);
        visit(node);
        inOrderTraversal(node.right);
    }
}

前序遍历：

void preOrderTraversal(TreeNode node){
    if(node != null){
        visit(node);
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }
}

后序遍历：

void postOrderTraversal(TreeNode node){
    if(node != null){
        postOrderTraversal(node.left);
        postOrderTraversal(node.right);
        visit(node);
    }
}

0.4 图的表示形式与搜索

图的表示方式：

图的搜索：

图的搜索
双向搜索

深度优先搜索（DFS）：

void search(Node root){
    if(root == null){
        return;
    }
    visit(root);
    root.visited = true;
    for each(Node n in root.adjacent){
        if(n.visited == false){
            search(n);
        }
    }
}

广度优先搜索（BFS）：

void search(Node root){
    Queue queue = new Queue();
    root.marked = true;
    queue.enqueue(root); //加入队尾
    
    while(!queue.isEmpty()){
        Node r = queue.dequeue(); //从队列头部删除
        visit(r);
        for each(Node n in r.adjacent){
            if(n.mark == false){
                n.marked = true;
                queue.enqueue(n);
            }
        }
    }
}

1. 节点间通路 [medium]

节点间通路

1.1 考虑点

1.2 解法

1.2.1 广度优先遍历法（优）

public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
    Queue<Integer> queue = new LinkedList<>();
    boolean[] isVisit = new boolean[n];
    isVisit[start] = true;
    queue.offer(start);
    while( !queue.isEmpty() ){
        int thisNode = queue.poll();
        int toNode;
        for(int i = 0; i < graph.length; i++){
            if(graph[i][0] == thisNode){
                toNode = graph[i][1];
                if(toNode == target){
                    return true;
                }
                if(!isVisit[toNode]){
                    isVisit[toNode] = true;
                    queue.offer(toNode);
                }
            }
        }
    }
    return false;
}

1.2.2 深度优先遍历法

private boolean[] visited = null;
public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
    this.visited = new boolean[graph.length];
    return helper(graph, start, target);
}

private boolean helper(int[][] graph, int start, int target) {
    for (int i = 0; i < graph.length; ++i) {
        // 确保当前路径未被访问（该判断主要是为了防止图中自环出现死循环的情况）
        if (!visited[i]) {
            // 若当前路径起点与终点相符，则直接返回结果
            if (graph[i][0] == start && graph[i][1] == target) {
                return true;
            }
            // 设置访问标志
            visited[i] = true;
            // DFS关键代码，思路：同时逐渐压缩搜索区间
            if (graph[i][1] == target && helper(graph, start, graph[i][0])) {
                return true;
            }
            // 清除访问标志
            visited[i] = false;
        }
    }
    return false;
}

1.2.3 邻接矩阵的幂的性质

public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
    int[][] adjacentMatrix = new int[n][n];
    for (int[] edge : graph) {
        adjacentMatrix[edge[0]][edge[1]] = 1;
    }
    for (int i = 1; i <= n; i++) {
        int[][] matrix = matrixPow(adjacentMatrix, i);
        if (matrix[start][target] != 0) {
            return true;
        }
    }
    return false;
}

public int[][] matrixPow(int[][] matrix, int n) {
    int size = matrix.length;
    int[][] res = new int[size][];
    for (int i = 0; i < size; i++) {
        res[i] = Arrays.copyOf(matrix[i], size);
    }
    for (int i = 1; i < n; i++) {
        for (int row = 0; row < size; row++) {
            int[] tmp = new int[size];
            for (int col = 0; col < size; col++) {
                for (int j = 0; j < size; j++) {
                    tmp[col] += res[row][j] * matrix[j][col];
                }
            }
            res[row] = Arrays.copyOf(tmp, size);
        }
    }
    return res;
}

1.2.4 当重复边为双向边时

public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
    int[] count = new int[n*(n-1)/2];
    for(int i = 0; i < graph.length; i++){
        int mark = (2*n-1-graph[i][0])*graph[i][0]/2-1+graph[i][1]-graph[i][0];
        count[mark]++;
        if(count[mark] == 2){
            int cache = graph[i][0];
            graph[i][0] = graph[i][1];
            graph[i][1] = cache;
        }
    }

    Queue<Integer> queue = new LinkedList<>();
    boolean[] isVisit = new boolean[n*(n-1)/2];
    queue.offer(start);

    while( !queue.isEmpty() ){
        int thisNode = queue.poll();
        int toNode;
        for(int i = 0; i < graph.length; i++){
            int mark = (2*n-1-graph[i][0])*graph[i][0]/2-1+graph[i][1]-graph[i][0];
            if(graph[i][0] == thisNode && !isVisit[mark]){
                toNode = graph[i][1];
                if(toNode == target){
                    return true;
                }
                queue.offer(toNode);
            }
        }
    }
    return false;
}

2. 最小高度树 [easy]

最小高度树

2.1 考虑点

2.2 解法

2.2.1 递归法（优）

public TreeNode sortedArrayToBST(int[] nums) {
    if(nums.length == 0){
        return null;
    }
    int l = 0;
    int r = nums.length-1;
    return recur(l, r, nums);
}

public TreeNode recur(int l, int r, int[] nums){
    if(l > r){
        return null;
    }
    int mid = (l+r)/2;
    int headVal = nums[mid];
    TreeNode head = new TreeNode(headVal);
    head.left  = recur(l, mid-1, nums);
    head.right = recur(mid+1, r, nums);
    return head;
}

2.2.2 BFS广度优先遍历

public TreeNode sortedArrayToBST(int[] num) {
    if (num.length == 0)
        return null;
    Queue<int[]> rangeQueue = new LinkedList<>();
    Queue<TreeNode> nodeQueue = new LinkedList<>();
    int lo = 0;
    int hi = num.length - 1;
    int mid = (lo + hi) >> 1;
    TreeNode node = new TreeNode(num[mid]);
    rangeQueue.add(new int[]{lo, mid - 1});
    rangeQueue.add(new int[]{mid + 1, hi});
    nodeQueue.add(node);
    nodeQueue.add(node);
    while (!rangeQueue.isEmpty()) {
        int[] range = rangeQueue.poll();
        TreeNode currentNode = nodeQueue.poll();
        lo = range[0];
        hi = range[1];
        if (lo > hi) {
            continue;
        }
        mid = (lo + hi) >> 1;
        int midValue = num[mid];
        TreeNode newNode = new TreeNode(midValue);
        if (midValue > currentNode.val)
            currentNode.right = newNode;
        else
            currentNode.left = newNode;
        if (lo < hi) {
            rangeQueue.add(new int[]{lo, mid - 1});
            rangeQueue.add(new int[]{mid + 1, hi});
            nodeQueue.add(newNode);
            nodeQueue.add(newNode);
        }
    }
    return node;
}

3. 特定深度节点链表 [medium]

特定深度节点链表

3.1 考虑点

3.2 解法

3.2.1 使用栈暴力法

public ListNode[] listOfDepth(TreeNode tree) {
    if(tree == null){
        return null;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(tree);
    int floor = 1; //第x-1层节点个数
    List<ListNode> listArr = new ArrayList<>();
    //当队列不为空
    while(!queue.isEmpty()){
        //按层处理
        int count = 0; //count用来储存第x层节点个数
        ListNode head = null;
        ListNode cur = null;
        for(int i = 0; i < floor; i++){
            TreeNode node = queue.poll();
            //创建链表
            if(i == 0){
                head = new ListNode(node.val);
                cur = head;
            } else {
                ListNode nodeL = new ListNode(node.val);
                cur.next = nodeL;
                cur = nodeL;
            }
            //加入队列
            if( node.left != null){
                count++;
                queue.offer(node.left);
            }
            if(node.right != null){
                count++;
                queue.offer(node.right);
            }
        }
        listArr.add(head);
        floor = count; //替换floor
    }
    ListNode[] list = new ListNode[listArr.size()];
    for(int i = 0; i < listArr.size(); i++){
        list[i] = listArr.get(i);
    }
    return list;
}

3.2.2 使用栈暴力法（代码优化缩短）

public ListNode[] listOfDepth(TreeNode tree) {
    if(tree == null){
        return null;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(tree);
    List<ListNode> listArr = new ArrayList<>();
    //当队列不为空
    while(!queue.isEmpty()){
        //按层处理
        int size = queue.size();
        ListNode head = new ListNode(0);
        ListNode cur = head;
        for(int i = 0; i < size; i++){
            TreeNode node = queue.poll();
            //创建链表
            cur.next = new ListNode(node.val);
            //加入队列
            if( node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
            cur = cur.next;
        }
        listArr.add(head.next);
    }
    return listArr.toArray(new ListNode[] {});
}

3.2.3 递归法（优）

public ListNode[] listOfDepth(TreeNode tree) {
    List<ListNode> list = new ArrayList<>();
    dfs(list, tree, 1);
    ListNode[] arr = new ListNode[list.size()];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = list.get(i);
    }
    return arr;
}
private void dfs(List<ListNode> list, TreeNode node, int deep) {
    if (node == null) {
        return;
    }
    if (deep > list.size()) {
        list.add(new ListNode(node.val));
    } else {
        ListNode n = list.get(deep - 1);
        while (n.next != null) {
            n = n.next;
        }
        n.next = new ListNode(node.val);
    }
    dfs(list, node.left, deep + 1);
    dfs(list, node.right, deep + 1);
}

4. 检查平衡性 [easy]

检查平衡性

4.1 考虑点

4.2 解法

4.2.1 自顶向下的递归

public boolean isBalanced(TreeNode root) {
    if(root == null){
        return true;
    }
    int deep = 1;
    int rootLeftDeep = findDeep(root.left, deep);
    int rootRightDeep = findDeep(root.right, deep);
    if(rootLeftDeep == -1 || rootRightDeep == -1){
        return false;
    }
    int result = Math.abs(rootLeftDeep - rootRightDeep);
    return result<2; 
}

public int findDeep(TreeNode node, int deep){
    if(node == null){
        return deep-1;
    }
    if(node.left == null && node.right == null){
        return deep;
    }
    deep++;
    int leftDeep = findDeep(node.left,deep);
    int rightDeep = findDeep(node.right,deep);
    int deepDiff = Math.abs(leftDeep-rightDeep);
    return deepDiff>1 ? -1 : Math.max(leftDeep,rightDeep);
}

4.2.2 自顶向下的递归

public boolean isBalanced(TreeNode root) {
    if (root == null) {
        return true;
    } else {
        return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
}

public int height(TreeNode root) {
    if (root == null) {
        return 0;
    } else {
        return Math.max(height(root.left), height(root.right)) + 1;
    }
}

4.2.3 自底向上的递归（优）

public boolean isBalanced(TreeNode root) {
    return height(root) >= 0;
}

public int height(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftHeight = height(root.left);
    int rightHeight = height(root.right);
    if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
        return -1;
    } else {
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

5. 合法二叉搜索树 [medium]

合法二叉搜索树

5.1 考虑点

5.2 解法

5.2.1 递归法

class Solution {
    Stack<Integer> stack = new Stack<>();
    boolean isFlag = false;
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }
        inOrderTraversal(root);
        return !isFlag;
    }

    public void inOrderTraversal(TreeNode node){
        if(isFlag){
            return;
        }
        if(node == null){
            return;
        }
        inOrderTraversal(node.left);
        if(stack.isEmpty()){
            stack.push(node.val);
        } else {
            if(stack.peek() >= node.val){
                isFlag = true;
                return;
            } else {
                stack.push(node.val);
            }           
        }
        inOrderTraversal(node.right);
    }
}

5.2.2 中序遍历非递归

public boolean isValidBST(TreeNode root) {
    Deque<TreeNode> stack = new LinkedList<TreeNode>();
    double inorder = -Double.MAX_VALUE;
    while (!stack.isEmpty() || root != null) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
            // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
        if (root.val <= inorder) {
            return false;
        }
        inorder = root.val;
        root = root.right;
    }
    return true;
}

5.2.3 中序遍历递归（优）

//前一个结点，全局的
TreeNode prev;

public boolean isValidBST(TreeNode root) {
    if (root == null)
        return true;
    //访问左子树
    if (!isValidBST(root.left))
        return false;
    //访问当前节点：如果当前节点小于等于中序遍历的前一个节点直接返回false。
    if (prev != null && prev.val >= root.val)
        return false;
    prev = root;
    //访问右子树
    if (!isValidBST(root.right))
        return false;
    return true;
}

6. 后继者 [medium]

后继者

6.1 考虑点

6.2 解法

6.2.1 中序遍历递归法

class Solution {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode findNode = null;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(root == null || p == null){
            return null;
        }
        inOrderTravarsal(root,p);
        return findNode!=null ? findNode : null;
    }

    public void inOrderTravarsal(TreeNode node, TreeNode p){
        if(findNode != null){
            return;
        }
        if(node == null){
            return;
        }
        inOrderTravarsal(node.left, p);
        if(stack.isEmpty()){
            stack.push(node);
        } else {
            if(p.equals(stack.peek())){
                findNode = node;
                stack.pop(); //忘记pop
                return;
            } else {
                stack.push(node);
            }
        }
        inOrderTravarsal(node.right, p);
    }
}

6.2.2 中序遍历非递归法（优）

public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    TreeNode pre = null;
    while(root.val!=p.val){
        //右边
        if(p.val > root.val){          
            root = root.right;
        }
        //左边
        else{   
            pre = root;
            root = root.left;
        }
    }
    //假如没有右子树
    if(root.right==null){
        return pre;
    } else {
        root = root.right;
        while(root.left!=null){
            root = root.left;
        }
        return root;
    }  
}

8. 首个共同祖先 [medium]

首个共同祖先

8.1 考虑点

8.2 解法

8.2.1 深度优先遍历

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root == null){
        return null;
    } else if(root.equals(p)){
        return p;
    } else if(root.equals(q)){
        return q;
    }
    TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
    TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
    if(leftNode == null && rightNode == null){
        return null;
    }
    if(leftNode != null && rightNode == null){
        if(leftNode.equals(q)){
            return q;
        } else if(leftNode.equals(p)){
            return p;
        } else {
            return leftNode;
        }
    }
    if(leftNode == null && rightNode != null){
        if(rightNode.equals(q)){
            return q;
        } else if(rightNode.equals(p)){
            return p;
        } else {
            return rightNode;
        }
    }
    //注意非空校验
    if((leftNode.equals(p) && rightNode.equals(q)) || (leftNode.equals(q) && rightNode.equals(p))){
        return root;
    } 
    return null;
}

8.2.2 深度优先遍历的简便写法（优）

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 到底了还没找到，返回 null
    if (root == null) {
        return null;
    }
    // 如果找到了 p 或 q，返回它
    if (root == p || root == q) {
        return root;
    }
    TreeNode left = lowestCommonAncestor(root.left, p, q);  
    TreeNode right = lowestCommonAncestor(root.right, p, q); 
    // 如果 left 和 right 都记录了找到的节点，那么肯定是一个记录了 p ，另一个记录了 q
    // 它们分别在以 root 为根的左右子树中，所以 root 就是它们的最近公共祖先
    if (left != null && right != null) {
        return root;
    }
    // 由于节点 p,q 一定在二叉树中，left和right不会同时为null
    // 若 left != null && right == null，说明在左子树中找到 p 或 q，而在右子树找不到 p 或 q，则剩下一个也在左子树
    // 所以 left 就是最近公共祖先
    // 另一种情况同理
    return (left != null) ? left : right;
}

9. 二叉搜索树序列 [hard]

二叉搜索树序列

9.1 考虑点

9.2 解法

9.2.1 回溯法+广度优先遍历

private List<List<Integer>> ans;

public List<List<Integer>> BSTSequences(TreeNode root) {
    ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    // 如果 root==null 返回 [[]]
    if (root == null) {
        ans.add(path);
        return ans;
    }
    List<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    // 开始进行回溯
    bfs(queue, path);
    return ans;
}

// 回溯法+广度优先遍历
private void bfs(List<TreeNode> queue, List<Integer> path) {
    // queue 为空说明遍历完了，可以返回了
    if (queue.isEmpty()) {
        ans.add(new ArrayList<>(path));
        return;
    }
    // 将 queue 拷贝一份，用于稍后回溯
    List<TreeNode> copy = new ArrayList<>(queue);
    // 对 queue 进行循环，每循环考虑 “是否 「将当前 cur 节点从 queue 中取出并将其左右子
    // 节点加入 queue ，然后将 cur.val 加入到 path 末尾」 ” 的情况进行回溯
    for (int i = 0; i < queue.size(); i++) {
        TreeNode cur = queue.get(i);
        path.add(cur.val);
        queue.remove(i);
        // 将左右子节点加入队列
        if (cur.left != null) queue.add(cur.left);
        if (cur.right != null) queue.add(cur.right);
        bfs(queue, path);
        // 恢复 path 和 queue ，进行回溯
        path.remove(path.size() - 1);
        queue = new ArrayList<>(copy);
    }
}

10. 检查子树 [medium]

检查子树

10.1 考虑点

10.2 解法

10.2.1 递归法（优）

boolean isFound =false;
public boolean checkSubTree(TreeNode t1, TreeNode t2) {
    if(t1 == null){
        return false;
    }
    if(t1.val == t2.val){
        isFound = true;
        return true;
    } else {
        isFound = false;
    }
    boolean left;
    boolean right;
    if(isFound){
        left = checkSubTree(t1.left, t2.left);
        right = checkSubTree(t1.right, t2.right);
        return left && right;
    } else {
        left = checkSubTree(t1.left, t2);
        right = checkSubTree(t1.right, t2);
        if(left){
            return checkSubTree(t1.left, t2);
        }
        if(right){
            return checkSubTree(t1.right, t2);
        }
    }
    return false;   
}

12. 求和路径 [medium]

求和路径

12.1 考虑点

12.2 解法

12.2.1 暴力法（优）

class Solution {
    int res = 0;

    public int pathSum(TreeNode root, int sum) {
        int dep = depth(root);
        int[] paths = new int[dep];
        pathSum(root, sum, 0, paths);
        return res;
    }
    public void pathSum(TreeNode root, int sum, int level, int[] paths) {
        if (root == null) {
            return;
        }
        paths[level] = root.val;
        int t = 0;
        for (int i = level; i >= 0; i--) {
            t += paths[i];
            if (t == sum) {
                res += 1;
            }
        }
        pathSum(root.left, sum, level + 1, paths);
        pathSum(root.right, sum, level + 1, paths);
    }
    public int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}

12.2.2 回溯法

private int res = 0;

public int pathSum(TreeNode root, int sum) {
    if(root == null) return res;

    helper(root, sum);
    pathSum(root.left, sum);
    pathSum(root.right, sum);
    return res;
}

private void helper(TreeNode node, int sum){
    if(node == null) return;

    sum -= node.val;
    if(sum == 0)
        res ++;
    helper(node.left, sum);
    helper(node.right, sum);
    sum += node.val;
}

最后

\color{blue}{\rm\small{新人制作，如有错误，欢迎指出，感激不尽！}}

\color{blue}{\rm\small{欢迎关注我，并与我交流！}}

\color{blue}{\rm\small{如需转载，请标注出处！}}

上一篇 下一篇

猜你喜欢

热点阅读