二叉树——好叶子节点对个数，求叶子节点之间的最短距离

落日映苍穹つ 2022-12-05 13:48 233阅读 0赞

给你二叉树的根节点 root 和一个整数 distance 。

如果二叉树中两个 叶 节点之间的 最短路径长度 小于或者等于 distance ，那它们就可以构成一组 好叶子节点对 。

返回树中 好叶子节点对的数量 。

示例 1：

输入：root = \[1,2,3,null,4\], distance = 3  
输出：1  
解释：树的叶节点是 3 和 4 ，它们之间的最短路径的长度是 3 。这是唯一的好叶子节点对。

示例 2：

输入：root = \[1,2,3,4,5,6,7\], distance = 3  
输出：2  
解释：好叶子节点对为 \[4,5\] 和 \[6,7\] ，最短路径长度都是 2 。但是叶子节点对 \[4,6\] 不满足要求，因为它们之间的最短路径长度为 4 。

示例 3：

输入：root = \[7,1,4,6,null,5,3,null,null,null,null,null,2\], distance = 3  
输出：1  
解释：唯一的好叶子节点对是 \[2,5\] 。

示例 4：

输入：root = \[100\], distance = 1  
输出：0

示例 5：

输入：root = \[1,1,1\], distance = 2  
输出：1

提示：

tree 的节点数在 [1, 2^10] 范围内。
    每个节点的值都在 [1, 100] 之间。
    1 <= distance <= 10

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/number-of-good-leaf-nodes-pairs  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这题自己不晓得咋做，看了许久别人的代码，茅塞顿开，主要思路就如leetcode官方题解说的，每个非叶子结点都可以看作是某一对叶子结点的公共祖先，我们需要求的是，这些公共祖先上的左右子树叶子结点配对后，有多少是小于等于distance的，把某个公共祖先结点的左子树上的叶子结点和右子树上的叶子结点（距离左子树和右子树的长度）分别装在两个数组中，之后将数组中的两个叶子结点的距离加起来再加上2，看是否小于等于distance。  
感觉有点难说清楚，还是读代码可能好懂一些，大概就是用两波前序遍历叭：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
     # include<iostream>
     # include<vector>
     using namespace std;
    class Solution { 
    public:
        int countPairs(TreeNode* root, int distance) { 
           if(root==NULL) return 0;
           int length=0;
           vector<int> lefts;
           countDepth(root->left,length,lefts);
           vector<int> rights;
           countDepth(root->right,length,rights);
           int res=0;
           for(int i=0;i<lefts.size();i++){ 
               for(int j=0;j<rights.size();j++){ 
                   if(lefts[i]+rights[j]+2<=distance) res++;
               }
           }
           res+=countPairs(root->left,distance);
           res+=countPairs(root->right,distance);
           return res;
        }
        void countDepth(TreeNode* root,int length,vector<int> &depthArray){ 
            if(root==NULL) return;
            if(root->left==NULL&&root->right==NULL){ 
                depthArray.emplace_back(length);
                return;
            }
            countDepth(root->left,length+1,depthArray);
            countDepth(root->right,length+1,depthArray);
        }
        
    };