Zeki's Blog
0%

二叉树的直径

Posted on

二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

1
2
3
4
5
6
7
8
9
给定二叉树

          1
         / \
        2   3
       / \     
      4   5    
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

思路1：计算最长路径，可以转化为求每个节点的作为根节点并该节点长度。并与全局变量max比较并更新。每个节点的最大长度等于其左子树最长的一条路径（左子树左右路径中较长的一条）+ 其右子树最长的一条路径（右子树左右路径中较长的一条）+ 1。 采用后续遍历，遍历过程中维护子树的左右子树最长路径，根据左右子树最长路径更新当前节点的左右最长路径。

官方思路：Max(max, 左子树深度+右子树深度+1)

思路1中的：”每个节点的最大长度等于其左子树最长的一条路径（左子树左右路径中较长的一条）+ 其右子树最长的一条路径（右子树左右路径中较长的一条）+ 1” 其实就是树的深度的意思，因为最终会遍历每一个节点作为根节点所以没必要维护左右子树的较大路径，直接用深度维护即可。

思路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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null) {
            return max;
        }
        find(root);
        return max;
    }

    public int[] find(TreeNode node) {
        int[] ret = new int[2];
        int min = 0;
        
        TreeNode left = node.left;
        TreeNode right = node.right;
        if(left == null && right == null) {
            return new int[]{1,1};
        }

        if(left != null) {
            int[] lv = find(left);
            ret[0] = Math.max(lv[0], lv[1]) + 1;
            min++;
        }
       
        if(right != null) {
            int[] lr = find(right);
            ret[1] = Math.max(lr[0], lr[1]) + 1;
            min++;
        }
        int l1 = ret[0] + ret[1] - min;
        max = Math.max(max, l1);
        return ret;
    }
}

官方解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans = 1;
        depth(root);
        return ans - 1;
    }
    public int depth(TreeNode node) {
        if (node == null) {
            return 0; // 访问到空节点了，返回0
        }
        int L = depth(node.left); // 左儿子为根的子树的深度
        int R = depth(node.right); // 右儿子为根的子树的深度
        ans = Math.max(ans, L+R+1); // 计算d_node即L+R+1 并更新ans
        return Math.max(L, R) + 1; // 返回该节点为根的子树的深度
    }
}

总结：最长路径就是以每个节点作为根节点，计算经过根节点的最长路径即可