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. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top