leetcode 543. 二叉树的直径（Java版）

以你之姓@ 2022-10-14 11:56 106阅读 0赞

## 题目 ##

[https://leetcode-cn.com/problems/diameter-of-binary-tree/][https_leetcode-cn.com_problems_diameter-of-binary-tree]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 1：暴力法 ##

暴力解法：遍历这棵树，当以每个节点为根时，计算 **距离**，取最大值作为最终结果。

其中，距离 = 左 **深度** \+ 右 **深度**。

其中，深度的计算用 `getDepth()` 来定义。

/* Definition for a binary tree node. */
    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;
         }
    }
    
    public class Solution { 
        int max = 0;
    
        public int diameterOfBinaryTree(TreeNode root) { 
            inOrder(root);
            return max;
        }
    	// 先序遍历
        public void inOrder(TreeNode node) { 
            if (node == null) return;
            int distance = getDepth(node.left, 0) + getDepth(node.right, 0);
            if (distance > max) max = distance;
            
            inOrder(node.left);
            inOrder(node.right);
        }
    	// 计算当前节点为根时的树深度
        public int getDepth(TreeNode node, int depth) { 
            if (node == null) return depth;
            else return Math.max(getDepth(node.left, depth + 1), getDepth(node.right, depth + 1));
        }
    }

此方法效率很差  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

## 题解 2：官方题解 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

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; // 返回该节点为根的子树的深度
        }
    }
    
    作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/diameter-of-binary-tree/solution/er-cha-shu-de-zhi-jing-by-leetcode-solution/

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

[https_leetcode-cn.com_problems_diameter-of-binary-tree]: https://leetcode-cn.com/problems/diameter-of-binary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221014/c3d1d6fc069440b3a646e28c5f55e350.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221014/63b3f090174d4d72af1d68ef2680f522.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20221014/ec3637c32c4a465daa091c6cbb9c9dc2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221014/32d60f063cae4ce5b16aee08053fd44d.png