求二叉树的最大直径

发表于 | 更新于 | 分类于 | 阅读次数： | 阅读次数：
本文字数： 977 | 阅读时长 ≈ 1 分钟

来源：https://blog.csdn.net/mine_song/article/details/69951308


　　

基本思想：

二叉树的直径：二叉树中从一个结点到另一个节点最长的路径，叫做二叉树的直径。

采用分治和递归的思想：
　　根节点为root的二叉树的直径 = Max(左子树直径，右子树直径，左子树的最大深度（不包括根节点）+右子树的最大深度（不包括根节点）+1)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    // 全局变量，用于记录最大直径
    int diameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        getDepth(root);
        return diameter;
    }

    // 此函数是返回树的最大深度
    private int getDepth(TreeNode root) {
        if (root == null) //作用1.传入实参非空判定； 
            return 0;      //作用2.若到达叶子结点就直接返回0（向下递归终止条件，开始向上返回递归）
        int l = getDepth(root.left); //向左递归
        int r = getDepth(root.right); //向右递归
        diameter = Math.max(diameter, l + r); //记录直径
        return Math.max(l, r) + 1; //返回结果
    }
}
---------------- The End ----------------
0%