leetcode543. 二叉树的直径

1.题目描述：

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。注意：两结点之间的路径长度是以它们之间边的数目表示。另注：子树较复杂时最长路径可以不穿过根节点，这道题目跟leetcode110.平衡二叉树类似，自顶向下，自底向上两种解法。

2.自顶向下递归：

首先理清解题的思路：与leetcode110.平衡二叉树一样，利用左右节点子树的高度来解决此题。递归的三步骤，①递归终止条件：root = null，返回0。②每级递归需要做什么：得到路径穿过当前节点的最长路径即左右子树高度之和，并且比较经过当前节点左子节点和右子节点的最长路径。③返回值：返回第二步中的三者的最大值。复杂度分析类似leetcode110.平衡二叉树。

class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        int max = depth(root.left) + depth(root.right);//这里返回边数，若节点数则需要+1
        int max1 = Math.max(diameterOfBinaryTree(root.left),diameterOfBinaryTree(root.right));
        return Math.max(max,max1);
    }
    public int depth(TreeNode curNode){
        return curNode == null ? 0 : Math.max(depth(curNode.left),depth(curNode.right)) + 1;
    }
}

3.自底向上递归：

在调用height方法的同时直接获得max值，只需遍历所有节点，时间复杂度和空间复杂度均为O(n)。

class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return max;
    }
    public int height(TreeNode curNode) {
        if (curNode == null) return 0;
        int l = height(curNode.left);
        int r = height(curNode.right);
        max = Math.max(max, l + r);
        return Math.max(l, r) + 1;
    }
}