C++ O(n) solution DFS using postorder traversal


  • 0
    S

    Basic idea is for each node calculate its left child's height and right child's height and update result when we get a larger value;
    notice we use postorder traversal so that we can get O(n) if it is preorder it will be O(n^2)

    int res;
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return res;
    }
    
    void dfs(TreeNode* root)
    {
        if(root==NULL) return ;
        dfs(root->left);
        dfs(root->right);
        res = max(res, height(root->left)+height(root->right));
    }
    
    int height(TreeNode* root)
    {
        if(root==NULL) return 0;
        if(root->left==NULL and root->right ==NULL) return 1;
        return max(height(root->left),height(root->right))+1;
    }

Log in to reply
 

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