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

  • 0

    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) {
        return res;
    void dfs(TreeNode* root)
        if(root==NULL) return ;
        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.