2020-07-11发表2022-11-15更新算法 / hash8 分钟读完 (大约1148个字)

Hash冲突解决方式

Hash冲突主要有两种解决办法，开放寻址法和链表法。这两种冲突解决办法在实际的软件开发中都非常常用。比如，Java 中 LinkedHashMap 就采用了链表法解决冲突，ThreadLocalMap 是通过线性探测的开放寻址法来解决冲突。那么这两种冲突解决方法各有什么优势和劣势，又各自适用哪些场景吗？

开放寻址法

我们先来看看，开放寻址法的优点有哪些。

开放寻址法不像链表法，需要拉很多链表。散列表中的数据都存储在数组中，可以有效地利用 CPU 缓存加快查询速度。而且，这种方法实现的散列表，序列化起来比较简单。链表法包含指针，序列化起来就没那么容易。你可不要小看序列化，很多场合都会用到的。我们后面就有一节会讲什么是数据结构序列化、如何序列化，以及为什么要序列化。

我们再来看下，开放寻址法有哪些缺点。

上一节我们讲到，用开放寻址法解决冲突的散列表，删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据。而且，在开放寻址法中，所有的数据都存储在一个数组中，比起链表法来说，冲突的代价更高。所以，使用开放寻址法解决冲突的散列表，装载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间。

所以，我总结一下，当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。

链表法

首先，链表法对内存的利用率比开放寻址法要高。因为链表结点可以在需要的时候再创建，并不需要像开放寻址法那样事先申请好。实际上，这一点也是链表优于数组的地方。

链表法比起开放寻址法，对大装载因子的容忍度更高。开放寻址法只能适用装载因子小于 1 的情况。接近 1 时，就可能会有大量的散列冲突，导致大量的探测、再散列等，性能会下降很多。但是对于链表法来说，只要散列函数的值随机均匀，即便装载因子变成 10，也就是链表的长度变长了而已，虽然查找效率有所下降，但是比起顺序查找还是快很多。

链表因为要存储指针，所以对于比较小的对象的存储，是比较消耗内存的，还有可能会让内存的消耗翻倍。而且，因为链表中的结点是零散分布在内存中的，不是连续的，所以对 CPU 缓存是不友好的，这方面对于执行效率也有一定的影响。

当然，如果我们存储的是大对象，也就是说要存储的对象的大小远远大于一个指针的大小（4 个字节或者 8 个字节），那链表中指针的内存消耗在大对象面前就可以忽略了。

实际上，我们对链表法稍加改造，可以实现一个更加高效的散列表。那就是，我们将链表法中的链表改造为其他高效的动态数据结构，比如跳表、红黑树。这样，即便出现散列冲突，极端情况下，所有的数据都散列到同一个桶内，那最终退化成的散列表的查找时间也只不过是 O(logn)。这样也就有效避免了前面讲到的散列碰撞攻击。

所以，我总结一下，基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

2020-01-10发表2022-11-15更新算法 / 字符串4 分钟读完 (大约570个字)

Boyer–Moore 字符搜索算法

因为字符比较是从右往左比较的，所以第一层循环 needle.length + 1 <= i < haystack.length。

                  start=needle.length - 1                                             end=haystack.length - 1
                          +                                                                   +
                          |                                                                   |
                          |                                                                   |
                          v-------------------------------------------------------------------v->
  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| t | h | i | s |   | i | s |   | a |   | s | i | m | p | l | e |   | e | x | a | m | p | l | e |
+-------------------------------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
+---------------------------+
| e | x | a | m | p | l | e |
+---+---+---+---+---+---+---+

第二层循环中i变量表示坏字符的位置、j表示搜索坏字符开始位置

                          i
                          +
                          |
                          v
  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| t | h | i | s |   | i | s |   | a |   | s | i | m | p | l | e |   | e | x | a | m | p | l | e |
+-------------------------------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
+---------------------------+
| e | x | a | m | p | l | e |
+---+---+---+---+---+---+-+-+
                          ^
                          |
                          +
                          j

i,j指针向左搜索,如果完全匹配直接返回i即可

for (j = needle.length - 1; needle[j] == haystack[i]; --i, --j) {
    if (j == 0) {
        return i;
    }
}

坏字符规则和好字符规则

坏字符:从右向左第一个不匹配的字符
好字符:从坏字符下一个字符直到最后的字符

可以认为字符移动有两种策略：坏字符对齐和好字符对齐，然后选择字符移动距离大的策略即可

wiki实现

/**
 * Returns the index within this string of the first occurrence of the
 * specified substring. If it is not a substring, return -1.
 *
 * There is no Galil because it only generates one match.
 *
 * @param haystack The string to be scanned
 * @param needle The target string to search
 * @return The start index of the substring
 */
public static int indexOf(char[] haystack, char[] needle) {
    if (needle.length == 0) {
        return 0;
    }
    int charTable[] = makeCharTable(needle);
    int offsetTable[] = makeOffsetTable(needle);
    for (int i = needle.length - 1, j; i < haystack.length;) {
        for (j = needle.length - 1; needle[j] == haystack[i]; --i, --j) {
            if (j == 0) {
                return i;
            }
        }
        // i += needle.length - j; // For naive method
        i += Math.max(offsetTable[needle.length - 1 - j], charTable[haystack[i]]);
    }
    return -1;
}

/**
 * Makes the jump table based on the mismatched character information.
 */
private static int[] makeCharTable(char[] needle) {
    final int ALPHABET_SIZE = Character.MAX_VALUE + 1; // 65536
    int[] table = new int[ALPHABET_SIZE];
    for (int i = 0; i < table.length; ++i) {
        table[i] = needle.length;
    }
    for (int i = 0; i < needle.length - 2; ++i) {
        table[needle[i]] = needle.length - 1 - i;
    }
    return table;
}

/**
 * Makes the jump table based on the scan offset which mismatch occurs.
 * (bad character rule).
 */
private static int[] makeOffsetTable(char[] needle) {
    int[] table = new int[needle.length];
    int lastPrefixPosition = needle.length;
    for (int i = needle.length; i > 0; --i) {
        if (isPrefix(needle, i)) {
            lastPrefixPosition = i;
        }
        table[needle.length - i] = lastPrefixPosition - i + needle.length;
    }
    for (int i = 0; i < needle.length - 1; ++i) {
        int slen = suffixLength(needle, i);
        table[slen] = needle.length - 1 - i + slen;
    }
    return table;
}

/**
 * Is needle[p:end] a prefix of needle?
 */
private static boolean isPrefix(char[] needle, int p) {
    for (int i = p, j = 0; i < needle.length; ++i, ++j) {
        if (needle[i] != needle[j]) {
            return false;
        }
    }
    return true;
}

/**
 * Returns the maximum length of the substring ends at p and is a suffix.
 * (good suffix rule)
 */
private static int suffixLength(char[] needle, int p) {
    int len = 0;
    for (int i = p, j = needle.length - 1;
             i >= 0 && needle[i] == needle[j]; --i, --j) {
        len += 1;
    }
    return len;
}

2019-11-20发表2022-11-15更新算法 / 排序3 分钟读完 (大约379个字)

LeetCode两个经典的排序算法

这回是标题党，记录下两个分而治之的排序算法（手写），分而治之的算法很容易改造成并行算法，肯定是未来的潮流， leetcode已通过，两个算法都使用了原地(inplace)更新。

class Solution {
    public List<Integer> sortArray(int[] nums) {
        // merge(nums, 0, nums.length - 1);
        sort(nums, 0, nums.length - 1);
        return IntStream.of(nums).boxed().collect(Collectors.toList());
    }

	//-------------------归并排序-------------------//
    private void merge(int[] nums, int start, int end) {
        if (start >= end) return;
        int midIdx = start + (end - start) / 2;
        merge(nums, start, midIdx);
        merge(nums, midIdx+1, end);
        concat(nums, start, midIdx, end);
    }

    private void concat(int[] nums, int start, int midIdx, int end) {
        int[] tmp = new int[end - start + 1];
        int lp = start, rp = midIdx + 1, i = 0;

        while (lp <= midIdx && rp <= end) {
            tmp[i++] = nums[lp] < nums[rp] ? nums[lp++] : nums[rp++];
        }

        while (lp <= midIdx) {
            tmp[i++] = nums[lp++];
        }

        while (rp <= end) {
            tmp[i++] = nums[rp++];
        }

        System.arraycopy(tmp, 0, nums, start, tmp.length);
    }

    // -------------------  归并排序 链表 ---------------------//

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists.length == 0) return null;
            return merge(lists, 0 , lists.length - 1);
        }

        private ListNode merge(ListNode[] lists, int low, int high) {
            if (low == high) return lists[low];

            int mid = (high - low) / 2 + low;

            return mergeLists( merge(lists, low, mid), merge(lists, mid+1, high));
        }

        public ListNode mergeLists(ListNode node1, ListNode node2) {
            if (node1 == null) return node2;
            if (node2 == null) return node1;

            if (node1.val < node2.val) {
                node1.next = mergeLists(node1.next, node2);
                return node1;
                
            } else {
                node2.next = mergeLists(node1, node2.next);
                return node2;
            }
        }
    }
    
    //-------------------快速排序-------------------//

    private void sort(int[] nums, int start, int end) {
        if (start >= end) return;

        int bIdx = partition(nums, start, end);
        sort(nums, start, bIdx - 1);
        sort(nums, bIdx + 1, end);
    }

    private int partition(int[] nums, int start, int end) {
        int idx = start, base = nums[end];

        for (int i = start; i < end; i++) {
            if (nums[i] < base) {
                swap(nums, idx++, i);
            }
        }
        swap(nums, idx, end);
        return idx;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

2019-08-10发表2022-11-15更新算法 / 字符串1 分钟读完 (大约147个字)

LeetCode 最长回文子串算法

Manacher 算法容易理解，实现起来也没什么大坑，复杂度还是 O(n)的，花半个小时实现下很有意思

class Solution {
    public String longestPalindrome(String s) {        
        StringBuilder sb = new StringBuilder(2 + 2 * s.length());
        sb.append("^");
        for (int i = 0; i < s.length(); i++) {
            sb.append("#").append(s.charAt(i));
        }
        sb.append("#$");
        
        String s2 = sb.toString();
        
        int maxStart = 1, max = 0, rC = 1, rR = 1;
        int[] p = new int[s2.length()];
        
        for (int i = 1; i < s2.length() - 1; i++ ) {
            
            p[i] = i < rR ? Math.min(p[2 * rC - i], rR - i) : 0;
            
            while (s2.charAt(i+p[i]+1) == s2.charAt(i - p[i] - 1)) {
                p[i] = p[i]+1;
            }
            
            if (i + p[i] > rR) {
                rC = i;
                rR = i + p[i];
            }
            
            if (p[i] > max) {
                maxStart = i - p[i];
                max = p[i];
            }
        }
        

        return s2.substring(maxStart,maxStart + 2*max+1).replace("#", "");
    }
}

2019-06-15发表2022-11-15更新算法 / 二叉树15 分钟读完 (大约2235个字)

LeetCode二叉树基础算法

树的高度

104. Maximum Depth of Binary Tree (Easy)

递归计算二叉树左右两边深度，取最大值。


/**

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }
}

平衡树

110. Balanced Binary Tree (Easy)

递归遍历二叉树左右子树深度

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    private boolean balance = true;
    
    public boolean isBalanced(TreeNode root) {
        visitTree(root);
        return balance;
    }
    
    private int visitTree(TreeNode root) {
        if (root == null) return 0;
        int left = visitTree(root.left);
        int right = visitTree(root.right);
        if (Math.abs(left - right) > 1 ) this.balance = false;
        return Math.max(left, right) + 1;
    }
}

两节点的最长路径

543. Diameter of Binary Tree (Easy)

递归遍历二叉树左右子树深度，路径就是两边子树深度之和

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    private int max;
        
    public int diameterOfBinaryTree(TreeNode root) {
        deep(root);
        return max;
    }
    
    private int deep(TreeNode root) {
        if (root == null) return 0;
        int left = deep(root.left);
        int right = deep(root.right);
        max = Math.max(max,left+right);
        return Math.max(left, right) + 1;
    }
}

翻转树

226. Invert Binary Tree (Easy)

递归交换左右子树的引用

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        TreeNode right =root.right;
        root.right = invertTree(root.left);
        root.left = invertTree(right);
        return root;
    }
}

归并两棵树

617. Merge Two Binary Trees (Easy)

递归时如果其中一个节点是空，可以直接复用该节点。如果新建节点，需要拷贝节点的左右子树引用，递归时会用到。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null ) return null;
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        TreeNode root =  new TreeNode(t1.val + t2.val);
        root.left = mergeTrees(t1.left, t2.left);
        root.right = mergeTrees(t1.right, t2.right);
        return root;
    }
}

判断路径和是否等于一个数

Leetcode : 112. Path Sum (Easy)

递归查询子树和是否等于目标和

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        if (root.val == sum && root.left == null && root.right == null) return true;
        return  hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

统计路径和等于一个数的路径数量

437. Path Sum III (Easy)

双层递归

以当前节点为起点统计路径和
当前节点以下节点为起点统计路径和

以root为根节点的路径数量= 以root为起点统计路径和+root左节点为起点统计路径和+root右节点为起点统计路径和

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        //结果数 等于 以当前root为父节点和 root以下为父节点结果数之和
        return sum(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    // 计算以当前node为父节点能都多少路径数
    private int sum(TreeNode node, int sum) {
        if (node == null) return 0;
        int count = 0;
        if (node.val == sum) count++;
        count += sum(node.left, sum - node.val) + sum(node.right, sum - node.val);
        return count;
    }
}

子树

572. Subtree of Another Tree (Easy)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null) return false;
        return isSubRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
    }
    
    public boolean isSubRoot(TreeNode node, TreeNode t) {
        if (node == null && t == null) return true;
        if (node == null || t == null) return false;
        if (node.val != t.val) return false;
        return isSubRoot(node.left, t.left) && isSubRoot(node.right, t.right); 
    }
}

树的对称

101. Symmetric Tree (Easy)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isSymmetric(root.left, root.right);
    }
    
    public boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
    }
}

最小路径

111. Minimum Depth of Binary Tree (Easy)

和最大路径类似

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if (left == 0 || right == 0) return left + right + 1;
        return Math.min(left, right) + 1;
    }
}

统计左叶子节点的和

404. Sum of Left Leaves (Easy)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        if (root.left != null && root.left.left == null && root.left.right == null) return root.left.val + sumOfLeftLeaves(root.right);
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }
}
````

#### 相同节点值的最大路径长度

[687. Longest Univalue Path (Easy)](https://leetcode.com/problems/longest-univalue-path/)

递归查找左右子树相同节点值最大路径，最大路径的计算：如果相等路径+1，如果不相等置为0。

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int path = 0;
    
    public int longestUnivaluePath(TreeNode root) {
        visit(root);
       return path; 
    }
    
    private int visit(TreeNode root) {
        if  (root == null) return 0;
        int left = visit(root.left);
        int right = visit(root.right);
        
        left =  (root.left != null && root.val == root.left.val) ? left + 1 : 0;
        right = (root.right != null && root.val == root.right.val)? right + 1 : 0;
        path = Math.max(path, left+right);
        return Math.max(left, right );
    }
}

间隔遍历

337. House Robber III (Medium)

递归查询两种情况

如果从当前节点开始
从当前节点的子节点开始

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        if (root == null) return 0;
        int val1 = root.val, val2 = 0;
        if (root.left != null) val1+= rob(root.left.left) + rob(root.left.right);
        if (root.right != null) val1+= rob(root.right.left) + rob(root.right.right);
        
        val2 = rob(root.left) + rob(root.right);
        return Math.max(val1, val2);
    }
}

找出二叉树中第二小的节点

Second Minimum Node In a Binary Tree (Easy)

第二小节点在子树节点上，如果子树值与根节点相等，继续向下查找

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) return -1;
        if (root.left == null) return -1;
        int left = root.left.val, right = root.right.val;
        if (root.val == root.left.val) left = findSecondMinimumValue(root.left);
        if (root.val == root.right.val) right = findSecondMinimumValue(root.right);
        if (left != -1 && right != -1) return Math.min(left, right);
        if (left > -1) return left;
        return right;
    }
}

二叉树的层平均值

637. Average of Levels in Binary Tree (Easy)

BFS

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> ret = new ArrayList<>();
        if (root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int count = queue.size();
            double sum = 0d;
            
            for(int i = 0; i < count; i++) {
                TreeNode node = queue.poll();
                sum+= node.val;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            ret.add(sum/count);
        }
        return ret;
    }
}

找树左下角的值

513. Find Bottom Left Tree Value (Easy)

DFS

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int val = 0;
    
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) return val;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            // 这一行的数量
            int count = queue.size();
            
            for (int i = 0; i < count; i++) {
                TreeNode node = queue.poll();
                if(i == 0) val = node.val;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return val;
    }
}

非递归实现二叉树的后序遍历

入栈条件：未访问过该节点
出栈条件：访问过该节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    private List<Integer> res = new LinkedList<>();
    private Stack<TreeNode> stack = new Stack<>();
    private Set<TreeNode> visited = new HashSet<>();
    
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) return res;
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            
            if ((node.left == null && node.right == null) || visited.contains(node)) {
                TreeNode i = stack.pop();
                res.add(i.val);
            } else {
                visited.add(node);
                if (node.right != null)
                    stack.push(node.right);
                if (node.left != null) 
                    stack.push(node.left);
            }
        }
        return res;
    }
    
    private void visit(TreeNode root) {
        if(root == null) return;
        visit(root.left);
        visit(root.right);
        res.add(root.val);
    }
}

非递归实现二叉树的前序遍历

入栈条件：无
出栈条件：直接出栈

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> res = new LinkedList<>();
    private Stack<TreeNode> stack = new Stack<>();
    
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) return res;
        stack.push(root);
        
        while (!stack.isEmpty()) {
                TreeNode node = stack.pop();
                res.add(node.val);
                if (node.right != null) stack.push(node.right);
                if (node.left != null)  stack.push(node.left);
        }
        return res;
    }
}

非递归实现二叉树的中序遍历

入栈条件：未访问过该节点
出栈条件：访问过该节点
入栈顺序: right -> middle -> left

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> res = new LinkedList<>();
    private Stack<TreeNode> stack = new Stack<>();
    private Set<TreeNode> visited = new HashSet<>();
    
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) return res;
        push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if ((node.left == null && node.right == null) || visited.contains(node)) {
                res.add(node.val);
            } else {
                push(node);
            }
        }
        return res;
    }
    
    private void push(TreeNode root) {
        if (root == null) return;
        visited.add(root);
        if (root.right != null) stack.push(root.right);
        stack.push(root);
        if (root.left != null) stack.push(root.left);
    }
}

2019-06-15发表2022-11-15更新算法 / 二叉树8 分钟读完 (大约1178个字)

LeetCode 二叉树排序树基础算法

修剪二叉搜索树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null) return null;
        if (root.val < L) return trimBST(root.right, L, R);
        if (root.val > R) return trimBST(root.left, L, R);
        root.left = trimBST(root.left, L, R);
        root.right = trimBST(root.right, L, R);
        return root;
    }
}

二叉搜索树中第K小的元素

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int cnt;
    private int val;
    
    public int kthSmallest(TreeNode root, int k) {
        search(root, k);
        return val;
    
    }
    
    private void search(TreeNode root, int k) {
        if (root == null) return;
        // 
        kthSmallest(root.left, k);
        cnt++;
        if (cnt == k) {
            val =  root.val;
            return;
        }
        kthSmallest(root.right, k);
    }
}

把二叉搜索树转换为累加树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    private int sum;
    
    public TreeNode convertBST(TreeNode root) {
        // 中序遍历 但是是从右往左遍历
        // 
        visit(root);
        return root;
    }
    
    
    private void visit(TreeNode root) {
        if (root == null) return;
        
        visit(root.right);
         sum += root.val;
    
        root.val = sum;
        
        visit(root.left);
    }
}

二叉搜索树的最近公共祖先

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 公共祖先在左边
        if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
        // 公共祖先在右边
        if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
        // 公共祖先在这
        return root;
    }
}

二叉树的最近公共祖先

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        // 左右都是父节点， 上一级就是公共父节点
        if(left != null && right != null) return root;
        if (left == null && right == null) return null;
        if (left != null) return left;
        return right;
    }
}

将有序数组转换为二叉搜索树

二叉树中序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length -1);
    }
    
    
    private TreeNode build(int[] nums, int start, int end) {
        
        if(start> end) return null;
        
        TreeNode node = new TreeNode(nums[(start+end)/2]);
        
        node.left = build(nums, start, (start+end)/2 -1);
        node.right = build(nums, (start+end)/2+1, end);
        return node;
    }
}

有序链表转换二叉搜索树

链表转数组

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> list = new LinkedList();
        ListNode now = head;
        while (now != null) {
            list.add(now.val);
            now = now.next;
        }
        
        return build(list, 0, list.size() - 1);
    }
    
    
    private TreeNode build(List<Integer> nums, int start, int end) {
        
        if(start> end) return null;
        
        TreeNode node = new TreeNode(nums.get((start+end)/2));
        
        node.left = build(nums, start, (start+end)/2 -1);
        node.right = build(nums, (start+end)/2+1, end);
        return node;
    }
}

还可以使用双指针找到链表中间节点，缺点是重复遍历节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
//         List<Integer> list = new LinkedList();
//         ListNode now = head;
//         while (now != null) {
//             list.add(now.val);
//             now = now.next;
//         }
        
//         return build(list, 0, list.size() - 1);
        
        return sortedListToBST(head, null);
        
        

    }
    
    private TreeNode sortedListToBST(ListNode head, ListNode tail) {
        if (head == tail) return null;
        
        ListNode mid = head, end = head;
        while (end != tail && end.next != tail) {
            mid = mid.next;
            end = end.next.next;
        }
        
        TreeNode root = new TreeNode(mid.val);
        root.right = sortedListToBST(mid.next, tail);
        root.left = sortedListToBST(head, mid);
        return root;
    }
    
    
    private TreeNode build(List<Integer> nums, int start, int end) {
        
        if(start> end) return null;
        
        TreeNode node = new TreeNode(nums.get((start+end)/2));
        
        node.left = build(nums, start, (start+end)/2 -1);
        node.right = build(nums, (start+end)/2+1, end);
        return node;
    }
    
}

两数之和 IV - 输入 BST

自己写两次遍历搜索二叉树，注意要排除自身节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private boolean res;
    private TreeNode r;
    private TreeNode current;
    
    
    public boolean findTarget(TreeNode root, int k) {
        r = root;
        visit(root, k);
        return res;
    }
    
    private void visit(TreeNode root, int val) {
        if (root == null) return;
        visit(root.left, val);
        current = root;
        if (find(r, val - root.val)) {res = true; return;}
        visit(root.right, val);
    }
    
    private boolean find(TreeNode root, int value) {
        if (root == null) return false;
        if (root == current) return false;
        if (root.val == value ) return true;
        return  (value > root.val) ? find(root.right, value): find(root.left, value);
    }
}

正经思路，中序遍历转化为排序数组，使用双指针查找

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    private List<Integer> res = new ArrayList<>(64);
    
    public boolean findTarget(TreeNode root, int k) {

        visitTree(root);
        
        int low = 0, high = res.size() - 1;
        while (low < high) {
            int sum = res.get(low) + res.get(high);
            if (sum == k) return true;
            if (sum < k) low++;
            else high--;
        }
        return false;
        
    }
    

    
    private void visitTree(TreeNode root) {
        if (root == null) return;
        visitTree(root.left);
        res.add(root.val);
        visitTree(root.right);        
    }

}

2018-11-11发表2021-08-23更新算法 / 字符串6 分钟读完 (大约948个字)

再谈最长公共子串

序言

这次遇到贝壳花名的需求，需要使用最长公共子串对花名做校验。这种算法在面试题中算是必会题，各种四层循环，三层循环，两层循环的代码在我脑中闪过，但是今天就是要带你实现不一样的最长公共子串！

教科书式实现

使用动态规划，两层循环，使用二维数组存储状态，时间复杂度O(n^2^)，空间复杂度O(n^2^)或O(2n)

一张图解释原理：

                  先 横 向 处 理
         +--------------------------->

           e   a   b   c   b   c   f
  +      +---+---+---+---+---+---+---+
  |    a | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
纵 |      +---------------------------+
向 |    b | 0 | 0 | 2 | 0 | 1 | 0 | 0 |
累 |      +---------------------------+
加 |    c | 0 | 0 | 0 | 3 | 0 | 2 | 0 |
  |      +---------------------------+
  |    d | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
  |      +---------------------------+
  |    e | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
  v      +---+---+---+---+---+---+---+
           e   a   b   c   b   c   f

优化空间复杂度至O(1)

从上图可以发现，在纵向累加时实际只需要左上方的计数器即可, O(n^2^)的空间白白被浪费了,最优的空间复杂度应该是O(1)。那么该如何处理呢？

一张图解释原理：

                                   e   a   b   c   b   c   f
    +---+                        +---+---+---+---+---+---+---+
  a | 0 |                            | 1 | 0 | 0 | 0 | 0 | 0 | a
    +-------+                        +-----------------------+
  b | 0 | 0 |                            | 2 | 0 | 1 | 0 | 0 | b
    +-----------+                        --------------------+
  c | 0 | 0 | 0 |                            | 3 | 0 | 2 | 0 | c
    +---------------+                        ----------------+
  d | 0 | 0 | 0 | 0 |                            | 0 | 0 | 0 | d
    +-------------------+                        +-----------+
  e | 1 | 0 | 0 | 0 | 0 |                            | 0 | 0 | e
    +---+---+---+---+---+-------+                    +---+---+
      e   a   b   c   b   c   f

答案就是沿着等长对着线处理。

有意思的代码抽象

大家可以根据上面思路写一下，一般会把算法分成两部分：处理长方形的左下部分和处理长方形的右上部分，两部分都是双层循环，时间复杂度和空间负载度已经变为了O(n^2^) ，O(1)。

肯定有人已经发现自己的代码处理左下角的代码和处理右上角的代码不能复用，一个是从中间向左下角处理，一个是从中间向右上角处理，明明很类似，但是就是没发合并。

那么有没有方法把这两部分处理抽象成公共代码呢？不卖关子了，直接上图：

                                                         +
                                                       e |
                                                         +--+
  e   a   b   c   b   c   f                            a | 1|
+---+---+---+---+---+---+---+                            +-----+
    | 1 | 0 | 0 | 0 | 0 | 0 | a                        b | 0| 2|
    +-----------------------+                            +--------+
        | 2 | 0 | 1 | 0 | 0 | b                        c | 0| 0| 3|
        --------------------+         翻      折           +-----------+
            | 3 | 0 | 2 | 0 | c     +------------>     b | 0| 1| 0| 0|
            ----------------+                            +--------------+
                | 0 | 0 | 0 | d                        c | 0| 0| 2| 0| 0|
                +-----------+                            +--------------+
                    | 0 | 0 | e                        f | 0| 0| 0| 0| 0|
                    +---+---+                            +--------------+
                                                           a  b  c  d  e

如果你想使用公共代码同时实现处理左下角和右上角是不可能的了。所以你需要把右上角的三角翻折，然后你就得到了两个三角：

                                      +
                                    e |
                                      +--+
                                    a | 1|
  +---+                               +-----+
a | 0 |                             b | 0| 2|
  +-------+                           +--------+
b | 0 | 0 |                         c | 0| 0| 3|
  +-----------+                       +-----------+
c | 0 | 0 | 0 |                     b | 0| 1| 0| 0|
  +---------------+                   +--------------+
d | 0 | 0 | 0 | 0 |                 c | 0| 0| 2| 0| 0|
  +-------------------+               +--------------+
e | 1 | 0 | 0 | 0 | 0 |             f | 0| 0| 0| 0| 0|
  +---+---+---+---+---+------         +--------------+
    e   a   b   c   b   c   f           a  b  c  d  e

这样就变成了处理两遍左下角了，代码也可以完美复用！！！

最终实现

我的完整思考过程已经分析完毕，这样沿对着线处理还有一个小小的优点：提前结束搜索。这一点大家可以自行思考，这里不做过多解释。

直接干货上场：

public class Solution {
    /**
     * @param A: A string
     * @param B: A string
     * @return: the length of the longest common substring.
     */
    public int longestCommonSubstring(String A, String B) {
        // write your code here
        char[] achars = A.toCharArray(), bchars = B.toCharArray();
        return getMaxLength(bchars, achars, getMaxLength(achars, bchars, 0, 0), 1);
    }
    
    private static int getMaxLength(char[] s1, char[] s2, int maxLength, int startIndex) {
        
        for (int start = startIndex; start < s1.length; start++) {
            int upper = Math.min(s2.length, s1.length - start);
            // if (upper <= maxLength) break; //提前结束搜索
            for (int currentLineLength = 0, x = 0, y = start; x < upper; x++, y++) {
                if (s1[y] == s2[x])
                    maxLength = Math.max(maxLength, ++currentLineLength);
                else {
                    // if (upper - x - 1 <= maxLength) break; //提前结束搜索
                    currentLineLength = 0;
                };
            }
        }
        return maxLength;
    }
}

结尾

怎么样，经历这次优化过程是否感觉自己对最长公共子串的认识又更深了一步呢？虽然不能保证是首创（也可能是首创？），但是这次一步一步真切思考优化直到获得成果让我无比兴奋。

说了这么多，我就是要给我们贝壳招聘开发组打个广告>_>，期待更多爱思考优秀的同学加入！

![](/Users/sage/Desktop/屏幕快照 2018-11-10 13.33.20.png)