【LeetCode】 543. 二叉树的直径 2020年3月10日

迷南。 2021-06-10 20:38 341阅读 0赞

## <table>   <tbody>    <tr>     <td><font>题目</font></td>    </tr>   </tbody>  </table> ##

题目传送门：[传送门（点击此处）][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]

## <table>   <tbody>    <tr>     <td><font>题解</font></td>    </tr>   </tbody>  </table> ##

### 思路 ###

从题目很容易想到，这道题要使用递归来做，每个节点要存储两个值，分别是 `左子树得深度` 和 `右子树得深度`，然后求得每个节点得直径即可

因为要遍历一遍节点，所以时间复杂度肯定是 `O(n)` ，空间复杂度是 `树的高度` ，因为用栈来做递归用，所以应该是 `O(Height)` ，最差是 `O(n)`

**至于难点就是，都要访问一个公共变量，所以这个变量抽离出来存储最大得直径**

### code ###

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; // 返回该节点为根的子树的深度
        }
    }

[Link 1]: https://leetcode-cn.com/problems/diameter-of-binary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUxNTMxMjgzMg_size_16_color_FFFFFF_t_70]: /images/20210529/dcc309eb9afd404b8a37f66276d18d29.png