543.二叉树的直径

问题

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

示例 : 给定二叉树

graph TD
    A[1] --- B[2]
    A --- C[3]
    B --- D[4]
    B --- E[5]

返回$3$,它的长度是路径 $[4,2,1,3]$ 或者 $[5,2,1,3]$。

**注意：**两结点之间的路径长度是以它们之间边的数目表示。

解法

此题是二叉树深度搜索的扩展，考虑设置一个全局变量result，每次递归时判断一次左子树深度+右子树深度 是否大于result，如果大于，那么将result替换成和，递归完成时，返回result即可。

代码

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int result = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        // 深度优先遍历+判断一次result大小即可。
        dfs(root);
        return result;
    }
    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //递归左子树
        int right = dfs(root.right);
        //递归右子树
        int left = dfs(root.left);
        //左子树深度+右子树深度就是走过当前节点的直径长度
        if (left + right > result) {
            result = left + right;
            
        }
        //返回当前节点深度+1.递归到上一层参与计算
        return Math.max(left, right) + 1;
    }
}