543. 二叉树的直径

Problem: 543. 二叉树的直径

思路

这道题目要求我们找到一棵二叉树中任意两个节点间最长路径的长度，这条路径可以经过树的根节点，也可以不经过。最长路径的长度即为树的直径。我们可以采用递归的方式来解决这个问题。

解题方法

定义一个辅助类 Info，其中包含两个成员变量，分别表示当前子树的高度和直径。使用递归函数 f 来遍历整个树，对于每个节点，我们先递归地获取其左右子树的信息，然后基于这些信息计算出当前节点的高度和直径，并返回。高度计算很简单，是左右子树高度的最大值加一。而直径则是三者中的最大值：左子树直径、右子树直径、以及左子树高度加上右子树高度。

复杂度

时间复杂度:

$O(n)$，其中$n$是树中节点的数量。每个节点只被访问一次。

空间复杂度:

$O(h)$，其中$h$是树的高度。递归栈的空间复杂度取决于树的形态，最坏情况下树是链状结构，空间复杂度为$O(n)$；最好情况下树是完全平衡的，空间复杂度为$O(logn)$。

Code

/**
 * 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 {
    public class Info{
        public int height;
        public int diameter;
        public Info(int height, int diameter ) {
            this.height = height;
            this.diameter = diameter;

        }
    }
    public int diameterOfBinaryTree(TreeNode root) {
        return f(root).diameter;
    }
    public Info f(TreeNode x) {
        if(x == null) {
            return new Info(0, 0);
        }
        Info infol = f(x.left);
        Info infor = f(x.right);
        int diameter = Math.max(Math.max(infol.diameter, infor.diameter), infol.height + infor.height);
        int height = Math.max(infol.height, infor.height) + 1;
        return new Info(height, diameter);
    }
}