LeetCode 543. Diameter of Binary Tree

543.Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longestpath between any two nodes in a tree. This path may or may not pass through the root.

Example: Given a binary tree

          1
         / \
        2   3
       / \     
      4   5    

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

题目大意:求一个二叉树中的任意两个节点的最长路径

解法一:

直接但是效率地下的解法,我们首先写一个求二叉树深度的函数depthTree(),求出二叉树的左右深度,依次遍历整个二叉树,就可以求出最大的深度。

public int diameterOfBinaryTree(TreeNode root) {
   if (root==null) return 0;
   return Math.max(depthTree(root.left)+depthTree(root.right),Math.max(diameterOfBinaryTree(root.left),diameterOfBinaryTree(root.right)));
}

public int depthTree(TreeNode root){
    if (root == null) return 0;
    return 1+Math.max(depthTree(root.right),depthTree(root.left));
}

解法二:

这个递归的设计是从下往上遍历二叉树的。left代表沿着root的左孩子的方向的深度,right代表沿着root的右孩子的方向的深度,二者相加就是顶点为root的一条最大路径。

class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        getDiameter(root);
        return max;
    }
    
    public int getDiameter(TreeNode root) {
        if (root == null) return 0;
        int left = getDiameter(root.left);
        int right = getDiameter(root.right);
        max = Math.max(max, left+right);
        return Math.max(left, right) + 1;  
    }
}

下面将getDiameter()函数加两个输出:

public int getDiamter(TreeNode root){
    if (root == null) return 0;
    int left = getDiamter(root.left);
    System.out.println(left);
    int right = getDiamter(root.right);
    System.out.println(right);
    max = Math.max(max,left+right);
    return Math.max(left,right)+1;
}

对于一个输入:

               5
//            / \
//           3   6
//          / \   
//         2   4   
          /
         1 

输出为:

0
0
1
0
2
0
0
1
3
0
0
1
4

示例:

         5
        / \
       3   6
      / \   
     2   4   
    / \
   1  null
  /  \
null null   0 0 1 0 2 0 0 1 3 0 0 1 4

这样可以很清楚的看到递归的过程。

不使用全局遍历的写法:

    public int diameterOfBinaryTree(TreeNode root) {
        int[] res = new int[1];
        getDiamter(root,res);
        return res[0];
    }
    public int getDiamter(TreeNode root,int[] res){
        if (root == null) return 0;
        int left = getDiamter(root.left,res);
        int right = getDiamter(root.right,res);
        res[0] = Math.max(res[0],left+right);
        return Math.max(left,right)+1;
    }

总结:对与二叉树的递归形式有很多,合适的递归方式可以有效的简化算法的复杂度。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏阿杜的世界

经典面试题之链表

9410
来自专栏武培轩的专栏

Java中Set集合是如何实现添加元素保证不重复的?

Java中Set集合是如何实现添加元素保证不重复的? Set集合是一个无序的不可以重复的集合。今天来看一下为什么不可以重复。 Set是一个接口,最常用的实现类就...

40670
来自专栏来自地球男人的部落格

[LeetCode] 39.Combination Sum

【原题】 Given a set of candidate numbers (C) (without duplicates) and a target ...

21870
来自专栏赵俊的Java专栏

二叉树层序遍历为二维数组

24630
来自专栏赵俊的Java专栏

二叉树的最大深度

22920
来自专栏Java爬坑系列

【Java入门提高篇】Day26 Java容器类详解(八)HashSet源码分析

  前面花了好几篇的篇幅把HashMap里里外外说了个遍,大家可能对于源码分析篇已经讳莫如深了。

11640
来自专栏tkokof 的技术,小趣及杂念

数学小记之数系

自然数即非负整数(包括 0 和 正整数),字母表示为 N(Natural number) :

20340
来自专栏决胜机器学习

PHP数据结构(八) ——赫夫曼树实现字符串编解码(理论)

PHP数据结构(八)——赫夫曼树实现字符串编解码(理论) (原创内容,转载请注明来源,谢谢) 一、树和森林 1、树的三种存储结构 1)双亲表示法——数组下标、值...

42790
来自专栏Jed的技术阶梯

普通树简介以及Java代码实现

88320
来自专栏朱慕之的博客

基础算法

0.创建类 BinaryTreeNode 1.创建方法:传入根结点 2.判断根节点是否为空 3.判断左右结点是否同时为空 4.用self调用此方法,将根节点的左...

7410

扫码关注云+社区

领取腾讯云代金券