![Leetcode 树-543-二叉树的直径 Leetcode 树-543-二叉树的直径](/default/index/img?u=aHR0cHM6Ly93d3cuaWNvZGU5LmNvbS9pL2xsLz9pPTIwMjEwMzAzMDk1NjUyOTk2LnBuZz8sdHlwZV9abUZ1WjNwb1pXNW5hR1ZwZEdrLHNoYWRvd18xMCx0ZXh0X2FIUjBjSE02THk5aWJHOW5MbU56Wkc0dWJtVjBMMU5NWDFkdmNteGssc2l6ZV8xNixjb2xvcl9GRkZGRkYsdF83MA==)
DFS解法
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
int max_len = 0;
public:
int dfs(TreeNode* root) {
// 叶节点返回深度0
int right = (root->left != nullptr) ? dfs(root->left) : 0;
int left = (root->right != nullptr) ? dfs(root->right) : 0;
int depth = max(left, right) + 1;
if (left + right > max_len)
max_len = left + right;
return depth;
}
int diameterOfBinaryTree(TreeNode* root) {
if (root == nullptr) return 0;
dfs(root);
return max_len;
}
};
![Leetcode 树-543-二叉树的直径 Leetcode 树-543-二叉树的直径](/default/index/img?u=aHR0cHM6Ly93d3cuaWNvZGU5LmNvbS9pL2xsLz9pPTIwMjEwMzAzMDk1NzM3ODI4LnBuZz8sdHlwZV9abUZ1WjNwb1pXNW5hR1ZwZEdrLHNoYWRvd18xMCx0ZXh0X2FIUjBjSE02THk5aWJHOW5MbU56Wkc0dWJtVjBMMU5NWDFkdmNteGssc2l6ZV8xNixjb2xvcl9GRkZGRkYsdF83MA==)