当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.543.Diameter of Binary Tree

LeetCode.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 longest path 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.


解题过程

一直就很害怕做树和图的题,太难了。在做了十几道简单LeetCode后,终于开始尝试做一道二叉树的题。为此专门复习了一下二叉树,下载了严蔚敏版的《数据结构》pdf。

求二叉树的直径,从来没遇见过,第一想法就是根结点的左子树深度加右子树深度,虽然题干中提示了路径不一定经过根结点,但感觉要想路径最长,肯定得过根结点才行。
第一版的代码如下:

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null)
            return 0;
        else
            return treeDepth(root.left) + treeDepth(root.right);//左子树深度+右子树深度
    }

    //递归计算二叉树的深度
    private int treeDepth(TreeNode root){
        if(root == null){
            return 0;
        }else{
            int rightDepth = treeDepth(root.right);
            int leftDepth = treeDepth(root.left);
            return rightDepth>leftDepth ? rightDepth+1 : leftDepth+1;
        }
    }
}

提交后出来个Wrong Answer,102 / 106 test cases passed.
过不去的测试用例是:
[4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2]

这里提一下LeetCode比较屌的功能,树结点遍历序列下有个“Visualize”,点击能可视化显示二叉树,非常方便,如下图:


LeetCode的树可视化功能

此外,点击代码编辑框右上角的”Debug code in playground”,在调试界面可以找到LeetCode提供的根据层次遍历序列创建二叉树的代码段,可直接拷贝下来用,方便我们自己在本地调试,如下:

//根据层次遍历序列创建二叉树
public static TreeNode stringToTreeNode(String input) {
    input = input.trim();
    input = input.substring(1, input.length() - 1);
    if (input.length() == 0) {
        return null;
    }

    String[] parts = input.split(",");
    String item = parts[0];
    TreeNode root = new TreeNode(Integer.parseInt(item));
    Queue<TreeNode> nodeQueue = new LinkedList<>();
    nodeQueue.add(root);

    int index = 1;
    while(!nodeQueue.isEmpty()) {
        TreeNode node = nodeQueue.remove();

        if (index == parts.length) {
            break;
        }

        item = parts[index++];
        item = item.trim();
        if (!item.equals("null")) {
            int leftNumber = Integer.parseInt(item);
            node.left = new TreeNode(leftNumber);
            nodeQueue.add(node.left);
        }

        if (index == parts.length) {
            break;
        }

        item = parts[index++];
        item = item.trim();
        if (!item.equals("null")) {
            int rightNumber = Integer.parseInt(item);
            node.right = new TreeNode(rightNumber);
            nodeQueue.add(node.right);
        }
    }
    return root;
}

然后继续说这道题。
认真看了看不通过测试用例的可视化图,发现以-9结点为根的子树的直径是8,看来我的思路是错的,最长路径不一定经过根结点,然后把代码改了改,递归的对左右子树算一下其左右子树深度之和,并与当前结点的左右子树深度之和比较,取较大者。

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null)
            return 0;
        else{
            int sumDepth = treeDepth(root.left) + treeDepth(root.right);//左右子树深度之和
            int leftSumDepth = diameterOfBinaryTree(root.left);//左子树的左右子树深度之和
            int rightSumDepth = diameterOfBinaryTree(root.right);//右子树的左右子树深度之和
            return Math.max(sumDepth, Math.max(leftSumDepth, rightSumDepth));//取较大者
        }
    }

    //递归计算二叉树的深度
    private int treeDepth(TreeNode root){
        if(root == null){
            return 0;
        }else{
            int rightDepth = treeDepth(root.right);
            int leftDepth = treeDepth(root.left);
            return rightDepth>leftDepth ? rightDepth+1 : leftDepth+1;
        }
    }
}

代码性能肯定是不行的,一有递归时间复杂度就高,更别说递归里面套递归,结果只打败了2.4%的代码。

然后看别人的代码,发现我的代码太繁琐了,大部分都是用一个全局变量来记录遍历过程中得到的最大左右子树深度之和,如下:

public class Solution {
    int max = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return max;
    }

    private int maxDepth(TreeNode root) {
        if (root == null) return 0;

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        max = Math.max(max, left + right);

        return Math.max(left, right) + 1;
    }
}

速度最快的也是这种方法。相比来说,我的代码整整多了一层循环,太低效了,用一个全局变量在求每个结点深度的过程中直接就能得出结果。

最后总结一下,这道题的思路是:经过每个结点的最长路径就是此结点的左右子树深度之和,但整个树的最长路径(也就是树的直径)并不一定经过根结点,所以要遍历所有结点,依次求其左右子树深度之和,记录下最大值就是树的直径。而求最大值的过程在计算树的深度过程中即可完成


GitHub代码


上一篇 LeetCode.389.Find the Difference

下一篇 LeetCode.136.Single Number

阅读
1,178
阅读预计5分钟
创建日期 2018-01-23
修改日期 2018-01-24
类别
百度推荐