[543. Diameter of Binary Tree] C++_Recursive_with brief explanation


  • 9

    We can solve this problem with two different cases:

    1. If the longest path will include the root node, then the longest path must be the depth(root->right) + depth (root->left)
    2. If the longest path does not include the root node, this problem is divided into 2 sub-problem: set left child and right child as the new root separately, and repeat step1.

    We could get the solution by returning the max path of 1 and 2.

    class Solution {
    public:
    int diameterOfBinaryTree(TreeNode* root) {
        if(root == nullptr) return 0;
        int res = depth(root->left) + depth(root->right);
        return max(res, max(diameterOfBinaryTree(root->left), diameterOfBinaryTree(root->right)));
    }
    
    int depth(TreeNode* root){
        if(root == nullptr) return 0;
        return 1 + max(depth(root->left), depth(root->right));
    }
    };

  • 0
    L
    This post is deleted!

  • 0
    Z

    What is the time complexity? Thanks!


  • 0
    S

    this is the truth. i missed the rule 2 which is the core key of the question.


  • 0
    W

    太棒啦!
    Bravo!
    Perfect!
    すごい!


  • 3
    M

    I am afraid this is not a good solution as there are duplicate visits of the tree nodes.


  • 0
    P

    @MitchellHe said in [543. Diameter of Binary Tree] C++_Recursive_with brief explanation:

    I am afraid this is not a good solution as there are duplicate visits of the tree nodes.

    I agree, this visits nodes twice. That isn't really needed here, though it does make the solution look neater I guess..


Log in to reply
 

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