二叉树的直径

原题链接

使用的方法

递归

解题思路

• 二叉树的直径是指树中任意两个节点之间最长路径的长度。这个路径可能经过根节点，也可能不经过根节点。
• 对于每个节点，我们可以计算以该节点为根的子树的深度，同时更新当前的最大直径。
• 递归的终止条件是当节点为 null 时，返回 0，表示当前节点没有子树。
• 在递归过程中，我们计算左子树和右子树的深度，并更新当前的最大直径为左子树深度加右子树深度的最大值。
• 最后返回当前节点的深度，即左子树深度和右子树深度的最大值加 1（表示当前节点本身）。

代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return res;
    }
    public int dfs(TreeNode node){
        if(node == null)
            return 0;
        int left = dfs(node.left);
        int right = dfs(node.right);
        res = Math.max(res,left+right);
        return Math.max(left,right)+1;
    }
}