力扣-543-二叉树的直径

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

例子:

力扣-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;  //当前节点的到叶子节点的最大深度
    }
}

 

上一篇:《缠中说禅108课》97:中医、兵法、诗歌、操作 1


下一篇:《缠中说禅108课》93:走势结构的两重表里关系 2