本文共 2017 字,大约阅读时间需要 6 分钟。
给你二叉树的根节点 root 和一个整数 distance 。
如果二叉树中两个 叶 节点之间的 最短路径长度 小于或者等于 distance ,那它们就可以构成一组 好叶子节点对 。
返回树中 好叶子节点对的数量 。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-good-leaf-nodes-pairs//** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { int count = 0; public int countPairs(TreeNode root, int distance) { if(root ==null) return 0; Tree tree = new Tree(root); tree.dfs(root.left,root.right,1,1 ,distance); count += tree.count; countPairs(root.left,distance); countPairs(root.right,distance); return count; } static class Tree { TreeNode root; int count; Tree(TreeNode root) { this.root = root;} void dfs(TreeNode left,TreeNode right,int dl,int dr,int depth) { //减枝,避免空指针 if(left==null ||right ==null || dl>depth || dr>depth) return; if(isLeaf(left) && isLeaf(right)) { if(dl+dr<=depth) count +=1; }else if(isLeaf(left)) { dfs(left,right.right,dl,dr+1,depth); dfs(left,right.left,dl,dr+1,depth); }else if(isLeaf(right)) { dfs(left.left,right,dl+1,dr,depth); dfs(left.right,right,dl+1,dr,depth); }else { //都不是叶子节点 dl++;dr++; dfs(left.left,right.right,dl,dr,depth); dfs(left.right,right.left,dl,dr,depth); dfs(left.left,right.left,dl,dr,depth); dfs(left.right,right.right,dl,dr,depth); } } boolean isLeaf(TreeNode root) { return root!=null && root.left==null && root.right==null; } }}
转载地址:http://pzyzi.baihongyu.com/