二叉树的直径

给定一颗二叉树，求二叉树的直径。

1.该题的直径定义为：树上任意两个节点路径长度的最大值

2.该题路径长度定义为：不需要从根节点开始，也不需要在叶子节点结束，也不需要必须从父节点到子节点，一个节点到底另外一个节点走的边的数目

3.这个路径可能穿过根节点，也可能不穿过

4.树为空时，返回 0

方法一：直接求解

具体方法

读完题目，其实最直接想到的方法就是直接求解。由于要求的树中两个节点的最大距离，所以可以求出根节点左侧的最大深度和右侧的最大深度，两者之和就可以得到树中距离最远的距离。

代码实现

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int diameterOfBinaryTree (TreeNode root) {
        if(root == null)
            return 0;
        //求出左侧最大深度
        int left = dfs(root.left);
        //求出右侧最大深度
        int rigt = dfs(root.right);
        int res = left+rigt;
        return Math.max(Math.max(res,diameterOfBinaryTree(root.left)),diameterOfBinaryTree(root.right));

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

复杂度分析

• 时间复杂度：$O(n)O(n)$，树的所有节点均被访问
• 空间复杂度：$O(height)O(height)$，$heightheight$为树的高度，递归的时候左右两侧的最大递归深度。

方法二：深度搜索

具体方法

方法一中是分别求出左右子树的高度，然后求和，也可以在深搜的过程中记录路径最长的结果。

一条路径的长度为该路径经过的节点数减一，所以求直径（即求路径长度的最大值）等效于求路径经过节点数的最大值减一。

而任意一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到。

代码实现

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int result;
    public int diameterOfBinaryTree(TreeNode root) {
        result = 1;
        depth(root);
        return result - 1;
    }
    public int depth(TreeNode root) {
        if (root == null) {
            return 0; // 访问到空节点了，返回0
        }
        int left = depth(root.left); // 左儿子为根的子树的深度
        int right = depth(root.right); // 右儿子为根的子树的深度
        result = Math.max(result, left+right+1); // 计算d_node即L+R+1 并更新ans
        return Math.max(left, right) + 1; // 返回该节点为根的子树的深度
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，树的所有节点均被访问
• 空间复杂度：$O(height)O(height)$，$heightheight$为树的高度，递归的时候左右两侧的最大递归深度。