leetcode 543. Diameter of Binary Tree 最长树的片段 + 深度优先遍历DFS

待我称王封你为后i 2022-06-03 03:41 146阅读 0赞

Given a binary tree, you need to compute 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.

Example:  
Given a binary tree  
1  
/ \\  
2 3  
/ \\  
4 5  
Return 3, which is the length of the path \[4,2,1,3\] or \[5,2,1,3\].

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

本题很简单就是在二叉树中寻找最长的片段，直接深度优先遍历即可

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    
    using namespace std;
    
    
    /*
    struct TreeNode 
    {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
     */
    
    class Solution 
    {
    public:
        int diameterOfBinaryTree(TreeNode* root) 
        {
            int res = 0;
            maxDepth(root, res);
            return res;
        }
    
        int maxDepth(TreeNode* root, int& res)
        {
            if (root == NULL)
                return 0;
            else
            {
                int left = maxDepth(root->left,res);
                int right = maxDepth(root->right,res);
                res = max(res, left + right);
                return max(left, right) + 1;
            }
        }
    };