长大后想做什么？做回小孩！

0%

LeetCode——二叉树的直径

发表于 更新于 分类于 Valine：
本文字数： 456

NO.543 二叉树的直径 简单

8iIWuT.png

思路一：深度优先遍历 这道题比较明显，立刻就能想到深度搜索，关键是怎么找到最长的。

一开始就陷入了一个误区，我觉着最大直径一定有根节点，所以根节点左子树找到最深的路径leftMax、右子树找到最深路径rightMax，最后总的最深路径就是leftMax+rightMax。很朴实的想法，但是明显是错误的。如果树是空的就错了，即使树不空但是根节点的左子树或者右子树为空也可能会出错，形如下图。

8izEL9.png

最初的这个想法浪费了不少时间，但是通过学习别人的思路发现最初的错误方法有一小部分是正确的。

虽然最大直径不一定经过根节点，但是一定经过某个节点(废话)，这个某节点的左子树最深路径和右子树最深路径之和就是最大直径。

我们要找的是路径和而不是节点和，这一点要牢记。

根据这个左右子树最大深度之和的方式，深度优先遍历将所有节点的最大直径都算出来，取最大即可。递归深搜到每个叶子节点，触底返回节点左右最深的路径+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int ans=0;
public int diameterOfBinaryTree(TreeNode root) {
    if (root==null)return ans;
    dfs(root);
    return ans;
}
private int dfs(TreeNode root) {
    //为空，没有路径
    if (root==null)return 0;
    //深搜
    int leftMax=dfs(root.left);
    int rightMax=dfs(root.right);
    //每个子树根的最大直径
    ans=Math.max(ans,leftMax+rightMax);
    //+1因为子树的根到父节点之间有一条边
    return Math.max(leftMax,rightMax)+1;
}

时间复杂度：O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github