tree


二叉树 Tree

  1. 先问清楚是不是二叉树?二叉搜索树?子节点到父节点的指针?
  2. 大部分题目可以通过递归解决
  3. 掌握四种遍历树的方法inorder, preorder, postorder, level order
  4. 配合遍历的顺序,有可能需要借助额外的数据结构,比如栈

one root

public Node solve(Node root) {
    if (root == null) 
        return null;
    Node l = solve(root.left);
    Node r = solve(root.right);
    return g(root, l, r);
}

two roots

public boolean solve(Node p, Node q) {
    if (p == null && q == null) 
        return true;
    if (p == null || q == null) 
        return false;
    if (p.val != q.val)
        return false;
    boolean l = solve(p.left, q.left);
    boolean r = solve(p.right, q.right);
    return l && r;
}

前缀树 Trie

  1. 终点节点的处理(这里的终点节点并不一定是叶子节点)
class TrieNode {  
    TrieNode[] children;  
    boolean isWord;  
    public TrieNode() {  
        children = new TrieNode[26];  
        isWord = false;  
    }  
}  

树状数组/二元索引树 Binary Indexed Tree

class BIT {
    int[] sum;
    public BIT(int n) {
        sum = new int[n+1];
    }

    public void update(int i, int diff) {
        while (i < sum.length) {
            sum[i] += diff;
            i += i & (-i);
        }
    }

    public int query(int i) {
        int res = 0;
        while (i > 0) {
            res += sum[i];
            i -= i & (-i);
        }
        return res;
    }
}

线段树 Segment Tree

  1. Each leaf node represents an element in the array.
    Each non leaf node covers the union of its children’s range.
class SegmentTreeNode {
    int start;
    int end;
    int sum;  // can be max or min
    SegmentTreeNode left;
    SegmentTreeNode right;
}
// time: O(n)
public SegmentTreeNode build(int start, int end, int[] vals) {
    if (start == end)
        return SegmentTreeNode(start, end, vals[start]);
    int mid = (start + end) / 2;
    SegmentTreeNode left = build(start, mid, vals);
    SegmentTreeNode right = build(mid+1, right, vals);
    return SegmentTreeNode(start, end, left.sum+right.sum, left, right);
}

// time: O(log n)
public void update(SegmentTreeNode root, int index, int val) {
    if (root.start == root.end && root.start == index) {  // a leaf node
        root.sum = val;
        return;
    }
    int mid = (start + end) / 2;
    if (index <= mid)
        update(root.left, index, val);
    else
        update(root.right, index, val);
    root.sum = root.left.sum + root.right.sum;
}

// time: O(log n + k)
public int query(SegmentTreeNode root, int l, int r) {
    if (root.start == l && root.end == j)
        return root.sum;
    int mid = (start + end) / 2;
    if (r <= mid)
        return query(root.left, l, r);
    else if (l > mid)
        return query(root.right, l, r);
    else 
        return query(root.left, l, mid) + query(root.right, mid+1, r);
}

Reference


Author: csy99
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source csy99 !
评论
 Previous
ml basic: 01 problem modeling ml basic: 01 problem modeling
问题建模1.1 评估指标线下使用机器学习评估指标,线上使用的是业务指标。需要进行多轮模型迭代使两个指标变化趋势相同。 1.1.1 分类指标精确率和召回率 用于二分类问题,结合混淆矩阵。 精确率 P = $\frac{TP}{T
Next 
greedy greedy
贪心算法 排序!如果是内置数据结构,直接使用自定义排序。排序之后考虑能否使用binary search。 Arrays.sort(arr, new Comparator<int[]>() { public int compa
2020-07-21
  TOC