543. Diameter of Binary Tree. (Easy)

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

 

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input: root = [1,2]
Output: 1

 

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -100 <= Node.val <= 100

A:

 利用C++ 的参数reference type, 来完成 多个 返回值

看helper(     , int & maxDepth)

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

*/

class Solution {

public:

int diameterOfBinaryTree(TreeNode* root) {

int maxDiameter = 0;

helper(root, maxDiameter);

return maxDiameter;

}

private:

int helper(TreeNode* root, int& maxVal) { // return depth of the tree

if (!root)

return 0;

int dl = helper(root->left, maxVal);

int dr = helper(root->right, maxVal);

if (dl + dr > maxVal) {

maxVal = dl + dr;

}

return 1 + max(dl, dr);

}

};