• API
• FAQ
• Tools
• Archive
SHARE
TWEET

Untitled

a guest Aug 17th, 2019 109 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /**
2.  * Definition for a binary tree node.
3.  * struct TreeNode {
4.  *     int val;
5.  *     TreeNode *left;
6.  *     TreeNode *right;
7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8.  * };
9.  */
10.
11. // 计算树的直径的长度
12. // 树的直径的定义是树上两个结点之间最长路径的长度
13. // 该路径可能经过，也可能不经过根结点
14.
15. class Solution {
16. public:
17.     int diameterOfBinaryTree(TreeNode* root) {
18.         int ans = 1;   // 初始化为 1 而不是 0 以应对边界情况
19.         depth(root, ans);
20.         return ans - 1;
21.     }
22.
23. private:
24.     // 求以 root 为根结点的子树的深度
25.     // 在搜索过程中，通过左右两子树的深度相加来更新已知的树的最大直径
26.     int depth(TreeNode* root, int& ans) {
27.         if(!root) return 0;
28.         int left = depth(root->left, ans);
29.         int right = depth(root->right, ans);
30.         ans = max(ans, left + right + 1);
31.         return max(left, right) + 1;
32.     }
33. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Not a member of Pastebin yet?