力扣-543-二叉树的直径

求一棵二叉树的直径长度：任意两个节点路径长度中的最大值。

例子：

在这棵二叉树中，直径长度是3，路径为[4 2 1 3]或者[5 2 1 3]。

从例子中我们可以看到，求二叉树的直径长度可以求左右子树的深度，最后求和即可。

而求左右子树的深度可以用深度优先搜索dfs。这条路径可能穿过也可能不穿过根结点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int res;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null){　　//如果是空树，直接返回0即可
            return 0;
        }
        res = 0;
        subtreeHeight(root);
        return res-1;
    }

    public int subtreeHeight(TreeNode node){
        if(node == null){　　//深度优先搜索到叶子结点的子节点时，直接返回0
            return 0;
        }
        int l = subtreeHeight(node.left);　　//求左子树的节点个数
        int r = subtreeHeight(node.right);　　//求右子树的节点个数
        res = Math.max(res, l+r+1);　　//路径是否穿过当前节点（max比较一下）
        return Math.max(l, r) + 1;　　//当前节点的到叶子节点的最大深度
    }
}

力扣-543-二叉树的直径

推荐阅读