leetcode865. 具有所有最深结点的最小子树

leetcode865. 具有所有最深结点的最小子树

三月 22, 2020

leetcode865. 具有所有最深结点的最小子树

给定一个根为 root 的二叉树，每个结点的深度是它到根的最短距离。

如果一个结点在整个树的任意结点之间具有最大的深度，则该结点是最深的。

一个结点的子树是该结点加上它的所有后代的集合。

返回能满足“以该结点为根的子树中包含所有最深的结点”这一条件的具有最大深度的结点。

示例：

输入：[3,5,1,6,2,0,8,null,null,7,4]
输出：[2,7,4]
解释：

在这里插入图片描述

我们返回值为 2 的结点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的结点。
输入 “[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]” 是对给定的树的序列化表述。
输出 “[2, 7, 4]” 是对根结点的值为 2 的子树的序列化表述。
输入和输出都具有 TreeNode 类型。

题目挺难理解的,多读几遍.这道题7和4是最深的,需要返回一个能包含他们的根节点,这个根节点也必须是最深的,所以返回2,不然2,5,3都能返回了.

思路

比较左右子树,如果深度一样,说明当前节点满足条件,否则哪个子树大,遍历哪个.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        return traverse(root);
    }
    public int depth(TreeNode root){
        if(root==null)return 0;
        return Math.max(depth(root.left),depth(root.right))+1;
    }
    public TreeNode traverse(TreeNode root){
        if(root==null)return null;
        int ldepth=depth(root.left);
        int rdepth=depth(root.right);
        if(ldepth==rdepth){
            return root;
        }else if(ldepth>rdepth){
            return traverse(root.left);
        }else {
            return traverse(root.right);
        }

    }
}

leetcode 60/100