LeetCode-543. 二叉树的直径

╰半橙微兮° 2024-03-27 14:08 77阅读 0赞

#### 目录 ####

*   *  题目分析
     *  错误实例
     *  正确实例

**题目来源**  
[543. 二叉树的直径][543.]

### 题目分析 ###

**1.如何求得两个叶子节点之间的路径长度**  
![在这里插入图片描述][64043741333a4444bb9202864c31b8ec.png]  
以a-> b表示从叶子结点a到叶子结点b的路径长度  
4->5 = （2->4）＋（2->5）  
4->3 = （1->4）＋（1->3）  
**两个叶子结点之间路径=根节点左右儿子的深度之和**

**根据思路写出表达式**  
Int depth(TreeNode root)//返回节点rt的深度  
4->3 = depth(结点1->左儿子)+ depth(结点1->右儿子);  
(注:以a-> b表示从叶子结点a到叶子结点b的路径长度)

**递归函数三要素:**  
1.子问题与原问题做同样的事  
2.需要有一个让递归结束的出口  
3.递归表达式  
![在这里插入图片描述][a21f9d9c417349beaa40166cb0ca96f7.gif_pic_center]

![在这里插入图片描述][933a0a04897b4a2d8bf1db7bc0bbb0c9.png]

### 错误实例 ###

class Solution {
        
    
        int ans = 0;
        public int diameterOfBinaryTree(TreeNode root) {
        
            ans = dfs(root.left)+dfs(root.right);
            return ans;
        }
    
        public int dfs(TreeNode root){
        
            if(root == null){
        
                return 0;
            }
            int left = dfs(root.left);
            int right = dfs(root.right);
            return Math.max(left,right)+1;
            
        }
    }

![在这里插入图片描述][7b77a90c9d6240ee9b834249f28579aa.png]  
一看错了的用例： \[4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2\] 可视化看看样子：  
![在这里插入图片描述][e8d114d21eec4738b5707bd5de8ebfa5.png]  
题目是说任意两个结点的路径 那么至少我找到了答案的那条线，是红色的这个，路径长度为8而不是7  
![在这里插入图片描述][aeebd54b94ca48e3b6f79423e2ddb5cf.png]

### 正确实例 ###

class Solution {
        
    
        int ans = 0;
        public int diameterOfBinaryTree(TreeNode root) {
        
            dfs(root);
            return ans;
        }
    
        public int dfs(TreeNode root){
        
            if(root == null){
        
                return 0;
            }
            int left = dfs(root.left);
            int right = dfs(root.right);
            ans = Math.max(ans,left+right);
            return Math.max(left,right)+1;
            
        }
    }

![在这里插入图片描述][1b488d8a40ce4f0d8093e8f0d29a7c7c.png]

[543.]: https://leetcode.cn/problems/diameter-of-binary-tree/
[64043741333a4444bb9202864c31b8ec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/f5b6bf28b00a4f0c975b7c59d01195e6.png
[a21f9d9c417349beaa40166cb0ca96f7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/fedf7e2cdbad44d58a3f0e70b5a89fe3.png
[933a0a04897b4a2d8bf1db7bc0bbb0c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/771733971f6045e783bd132a9328a819.png
[7b77a90c9d6240ee9b834249f28579aa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/c0a3de0bdd8f4d3a942931ce1f2931f6.png
[e8d114d21eec4738b5707bd5de8ebfa5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/0072022677d24b82a57ef15137d7b001.png
[aeebd54b94ca48e3b6f79423e2ddb5cf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/9cb708eb7c7545568e3fc3dc887e7cce.png
[1b488d8a40ce4f0d8093e8f0d29a7c7c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/f98ae62b2a1e471a897b3d1e4bbfa69a.png