字典树/前缀树

所谓的字典树其实就是一颗多叉树,通常来说,就是每一个节点存一个字符(或者数字等),通过这个节点存的值,指向子节点。

字典树和哈希表通常都可以用来进行字符串的比较,它们的复杂度差距并不明显,在不同的场景下可能都可以使用,也可能另一个效率更高。

通常,涉及到普通的字符串匹配,就可以用哈希表,而涉及前后缀,提前给定非常多的字符串等题,就可以考虑使用字典树了。

回文对

给一独特的单词列表, 在给定列表中查找所有不同的索引 (i, j) 对, 使得两个单词的串联即 words[i] + words[j] 是回文串。

输入:
["abcd", "dcba", "lls", "s", "sssll"]
输出:
[[0, 1], [1, 0], [3, 2], [2, 4]]

解释:
回文串为 `["dcbaabcd", "abcddcba", "slls", "llssssll"]`

题解:

对于每一个单词:

  • 如果单词的左侧是回文,右侧的 reverse() 也在 Trie 树/哈希表里面,说明可以构成回文对 (见下文图示)
  • 如果单词的右侧是回文,左侧的 reverse() 也在 Trie 树/哈希表里面,说明可以构成回文对

hui_wen_dui

二叉树的最近公共祖先

  • 先看孩子是否有可能是公共祖先,最后看树根有没有可能是公共祖先。因为树根总是祖先。是用来兜底的。
  • rootp 的祖先,那么 proot 的子系亲属或者孙子系亲属,即向下的亲属关系。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root != null) {
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        if (left != null) {
            return left;
        }

        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (right != null) {
            return right;
        }

        if (isSubNode(root, p) && isSubNode(root, q)) {
            return root;
        }
    }

    return null;
}

private boolean isSubNode(TreeNode root, TreeNode p) {
    if (root == null) {
        return false;
    }

    if (root.val == p.val) {
        return true;
    }

    return isSubNode(root.left, p) || isSubNode(root.right, p);
}

BST 第 K 大的数字

二叉搜索树的中序遍历为递增序列。因此这道题可转化为求 “此树的中序遍历倒序的第 k 个节点”。

class Solution {
    
    int res, k;
    
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }
 
    void dfs(TreeNode root) {
        if (root == null) 
            return;

        dfs(root.right);

        if (k == 0) 
            return;

        if (--k == 0) 
            res = root.val;

        dfs(root.left);
    }

}

时间复杂度:O(N),空间复杂度:O(N),当树退化为链表(全部是右节点)的时候,系统使用 O(N) 大小的栈空间。

BST 中序遍历的下一个节点

这道题是 《剑指 Offer》 上的题目,先确定有无指向父节点的指针?

二叉树的最小深度

最小深度是从根节点最近叶子节点的最短路径上的节点数量。

  • 这道题有一定技巧性
public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }

    if (root.left == null) {
        return minDepth(root.right) + 1;
    }

    if (root.right == null) {
        return minDepth(root.left) + 1;
    }

    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}

二叉树中所有距离为 K 的结点

字节、WXG 都面过。

原题的意思是,给定目标节点 target,返回这棵树上距离 target 路径长度为 K 的所有 TreeNode 节点。

思路:

  • 使用 Map 实现根据子节点 O(1) 时间快速找到 parent 节点的目的。
  • 层次遍历,只不过不是从 root 开始,而是从 target 节点开始,以 target 节点向 parentchild 扩展,直到第 K 层。扩展的过程使用 Set 进行去重。
  • 到达第 K 层之后,当前 Queue 里面所剩的就是结果。
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
    if (K == 0) {
        List<Integer> list = new ArrayList();
        list.add(target.val);
        return list;
    }

    Map<TreeNode, TreeNode> childParentMap = new HashMap<>();
    buildParentMap(root, null, childParentMap);

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(target);

    Set<TreeNode> set = new HashSet<>();
    set.add(target);

    int level = 0;
    while (!queue.isEmpty()) {

        int size = queue.size();
        if (level == K) {
            List<Integer> list = new ArrayList<>(size);

            for (int i = 0; i < size; i++) {
                list.add(queue.poll().val);
            }

            return list;
        } else if (level < K) {
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                set.add(curr);
                
                TreeNode parent = childParentMap.get(curr);

                if (parent != null && !set.contains(parent)) {
                    queue.offer(parent);
                }

                if (curr.left != null && !set.contains(curr.left)) {
                    queue.offer(curr.left);
                }

                if (curr.right != null && !set.contains(curr.right)) {
                    queue.offer(curr.right);
                }
            }

            level++;
        } else {
            break;
        }
    }

    return Collections.emptyList();
}

// 遍历整棵树,构建父子关系的 Map 图
private void buildParentMap(TreeNode node, 
                            TreeNode parent, 
                            Map<TreeNode, TreeNode> childParentMap) {
    if (node != null) {
        childParentMap.put(node, parent); // node's parent is parent
        buildParentMap(node.left, node, childParentMap);
        buildParentMap(node.right, node, childParentMap);
    }
}

二叉树的中序遍历

二叉树中的最大路径和

路径不一定经过 root

思路,针对一个节点,我们有如下几种路径可以选择:

  • root.val
  • 左子树的最大路径和 + root.val
  • 右子树的最大路径和 + root.val
  • 左子树的最大路径和 + root.val + 右子树的最大路径和

我们的递归函数返回的值,只能是如下几种形状:

[root]

   [root]
     /
[left-child]

  [root]
     \
 [right-child]

为什么只能是如上三种形状,是因为递归返回之后,这三种形状可以继续和另外递归返回的值继续构成路径。如果返回的是:

        [root]
       /      \
[left-child] [right-child]

那么该形状无法与其他的边构成路径,不是合法的路径,就会导致后面继续递归、相加其他值出现错误。就像下图示例

   [-10]
  /    \
[9]    [20]
      /   \
   [15]   [7]

站在 [20] 这个节点上,我们只能返回 [20][20] - [15][20] - [7] 这三条路径,[15] - [20] - [7] 智能作为中间的值来去计算。返回这三条路静,我们才能够继续跟 [10] 进行连接,继续递归求值。

另外对于左/右子树返回的值,我们应该考虑其值是否对于最终的 max 有增益性,如果其本身返回的就是负值,那么还不如不加。

private int max = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    dfs(root);
    return max;
}

public int dfs(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int leftMaxSum = Math.max(dfs(root.left), 0);
    int rightMaxSum = Math.max(dfs(root.right), 0);

    max = Math.max(max, leftMaxSum + root.val + rightMaxSum);

    return Math.max(root.val, Math.max(leftMaxSum + root.val, rightMaxSum + root.val));
}

验证二叉搜索树

// =========================
// 两个递归
// - 每一个节点是否是一个有效的 BST
// - 一个节点的值,是否大于等于所有左子树的值,是否小于等于所有右子树的值
// =========================

public boolean isValidBST(TreeNode root) {
    if (root == null) {
        return true;
    }

    boolean rootValid = isLeftTreeValid(root.val, root.left) && isRightTreeValid(root.val, root.right);
    boolean childValid = isValidBST(root.left) && isValidBST(root.right);
    return rootValid && childValid;
}

private boolean isLeftTreeValid(int rootVal, TreeNode leftTree) {
    if (leftTree == null) {
        return true;
    }

    if (rootVal <= leftTree.val) {
        return false;
    }

    return isLeftTreeValid(rootVal, leftTree.left) && isLeftTreeValid(rootVal, leftTree.right);
}

private boolean isRightTreeValid(int rootVal, TreeNode rightTree) {
    if (rightTree == null) {
        return true;
    }

    if (rootVal >= rightTree.val) {
        return false;
    }

    return isRightTreeValid(rootVal, rightTree.left) && isRightTreeValid(rootVal, rightTree.right);
}

路径和

public boolean hasPathSum(TreeNode root, int sum) {
    return hasPathSum(root, 0, sum);
}

private boolean hasPathSum(TreeNode root, int cur, int sum) {
    // ======================
    // 处理 root 这个节点
    // ======================
    if (root == null) {
        return false;
    }

    if (root.left == null && root.right == null && cur + root.val == sum) {
        return true;
    }

    // ======================
    // 处理 root.left、root.right 这两个个节点
    // ======================
    return hasPathSum(root.left, cur + root.val, sum) ||
        hasPathSum(root.right, cur + root.val, sum);
}

路径和 2

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> result = new ArrayList<>();
    pathSum(root, result, new ArrayList<Integer>(), 0, sum);
    return result;
}

private void pathSum(TreeNode root, List<List<Integer>> result, List<Integer> curList, int cur, int sum) {
    if (root == null) {
        return;
    }

    curList.add(root.val);

    if (root.left == null && root.right == null && cur + root.val == sum) {
        result.add(new ArrayList<Integer>(curList));
    }

    if (root.left != null) {
        pathSum(root.left, result, curList, cur + root.val, sum);
    }

    if (root.right != null) {
        pathSum(root.right, result, curList, cur + root.val, sum);
    }

    curList.remove(curList.size() - 1);
}