A question of the day — trees

Number of good leaf node pairs

Number of good leaf node pairs

Analysis of the

  1. When judging by distance, we first look at whether BFS is used to compare in one layer, or DFS is used to compare from a tree node to a hub node, and then to another tree node
  2. Since hub nodes are needed and leaf nodes are compared, it is necessary to use preorder traversal to obtain all values of distance between hub nodes and leaf nodes from bottom up.
  3. Since it is from one leaf node to another leaf node, the hub node must also be divided into the left and right subtree distance array and matched separately
// https://leetcode-cn.com/problems/number-of-good-leaf-nodes-pairs/description/
// 1530. Number of good leaf node pairs
[1530.Number of good leaf node pairs]()/** * @ * 1. The number of good pairs of nodes that need to be matched, not to find, or exist * 2. So to calculate the quantity, you have to have the corresponding data pool, and then compare the combination to get the quantity that matches the specification * 3. In this case, it is the path match between leaf nodes, so the datapool is: the distance between the current node and each leaf node * 4. Since it is the shortest distance, it is best to find it from the bottom up, so use the preorder to traverse the leaf nodes to * 5. Then, from the bottom up, we can infer the array * 6 of the distance between the left and right subtrees according to the distance between the left and right subtrees and the leaf nodes. Since each node is a connection hub, the number of node pairs divided by the left and right distance array can be matched */
var countPairs = function (root, distance) {
    let res = 0
    const dfs = root= > {
        if(! root)return []
        if(! root.left && ! root.right)return [0]
        // Find the array of distances to the left leaf node
        const leftArr = dfs(root.left).map(i= > i+1)
        // Find the array of distances to the right leaf node
        const rightArr = dfs(root.right).map(i= > i+1)
        // Root is the connection hub, all matches must go through it to connect.
        for (let l of leftArr) {
            for (let r of rightArr) {
                if(l+r<=distance){
                    res++
                }
            }
        }
        // Finally, return an array of distances from the current node to all leaf nodes
        return [...leftArr,...rightArr]
    }
    dfs(root)
    return res
};

Copy the code