LeetCode 543. Diameter of Binary Tree

原创

大学里的混子

修改于 2018-10-30 07:02:07

62800

代码可运行

文章被收录于专栏：LeetCodeLeetCode

运行总次数：0

代码可运行

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

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

输出为：

示例：

         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;
    }