【LeetCode】543.二叉树的直径

1 问题

给你一棵二叉树的根节点，返回该树的直径。

二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的长度由它们之间边数表示。

示例 1

输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2

输入：root = [1,2]
输出：1

提示

• 树中节点的数目在范围 [1, $10^4$] 内
• -100 <= Node.val <= 100

2 解题思路

2.1 双递归

• 先写出计算树的高度的算法height(root)
• 计算当前节点可能的直径，其等于height(root.left)+height(root.right)，并记录当前的最大直径max
• 计算左右子树的直径（因为题目说了，不一定经过根节点），找出最大的那个childMaxLength，Math.max(max, childMaxLength)即为当前节点的最大直径。

  详见代码：diameterOfBinaryTree2()。

2.2 单递归

优化下代码，只需要一个递归方法即可，原理与2.1差不多。

详见代码：diameterOfBinaryTree()。

3 代码

/**
 * 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 max=Integer.MIN_VALUE;
    public int diameterOfBinaryTree2(TreeNode root) {
        if(null==root){
            return 0;
        }
        int h=Math.max(max, height(root.left)+height(root.right));
        int childMaxLength=Math.max(diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right));
        return Math.max(h, childMaxLength);
    }


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

    //one recursive
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return max;
    }

    private int dfs(TreeNode root){
        if(null==root){
            return 0;
        }
        //left and right tree's height
        int leftH=dfs(root.left);
        int rightH=dfs(root.right);
        //current max height
        max=Math.max(max, leftH+rightH);
        //current node's height
        return Math.max(leftH, rightH)+1;
    }
}