本文共 1357 字,大约阅读时间需要 4 分钟。
给定一个根为 root 的二叉树,每个结点的深度是它到根的最短距离。
如果一个结点在整个树的任意结点之间具有最大的深度,则该结点是最深的。
一个结点的子树是该结点加上它的所有后代的集合。
返回能满足“以该结点为根的子树中包含所有最深的结点”这一条件的具有最大深度的结点。
示例:
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/smallest-subtree-with-all-the-deepest-nodes 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。/** * 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 { public TreeNode subtreeWithAllDeepest(TreeNode root) { if(root == null) return null; //最深节点的父亲节点 // Tree tree = new Tree(root); int dl = Tree.depth(root.left); int dr = Tree.depth(root.right); if(dl==dr) return root; if(dl>dr) { return subtreeWithAllDeepest(root.left); }else{ return subtreeWithAllDeepest(root.right); } } static class Tree { // TreeNode root = null; // Tree(TreeNode root) {this.root = root;} static int depth(TreeNode root) { if(root ==null) return 0; return Math.max(depth(root.left),depth(root.right))+1; } }}