C++ O(n) DFS Approach


  • 0
    Z
    /**
     * 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 {
    public:
        int result = 0;
        int diameterOfBinaryTree(TreeNode* root) {
            
            dfs(root);
            
            return result;
        }
        
        int dfs(TreeNode* root){
            
            if(root==nullptr)
                return 0;
                
            int left = dfs(root->left);
            int right = dfs(root->right);
            
            if(left+right>result)
                result = left+right;
            
            return left>right? left+1:right+1;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.