543. Diameter of Binary Tree

发布时间：2020-12-14 04:40:58 所属栏目：大数据来源：网络整理

导读：一、题目 1、审题 ? 2、分析求一棵二叉树中两个节点相连的路径中的最多的边数。 ? 二、解答 1、思路等价于求一个节点作为根节点时，Max (左孩子的深度 + 右孩子深度). ① 、采用全局变量 max 记录 Max(左孩子深度 + 右孩子深度) ②、新建一个 getMaxDepth

一、题目

　　1、审题　

　　2、分析

　　　　求一棵二叉树中两个节点相连的路径中的最多的边数。

二、解答

　　1、思路

　　　　等价于求一个节点作为根节点时，Max (左孩子的深度 + 右孩子深度).

　　　　① 、采用全局变量 max 记录 Max(左孩子深度 + 右孩子深度)

　　　　②、新建一个 getMaxDepth（root）方法，该方法返回此 root 节点的最大深度（为左子树深度或右子树深度 + 1）

　　　　　　同时，方法体内更新 max 值；

    int max = 0;
    // 最长的左子树的深度 + 右子树的深度
    public int diameterOfBinaryTree(TreeNode root) {
        getMaxDepth(root);
        return max;
    }

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!