AC with C++ -- traverse and sum height left right


  • 0
    T

    AC but not the optimal solution. The trick is to calculate the sum of the maximum left height and the maximum right height for each node in the tree; thus we have to traverse the tree also.

    int diameterOfBinaryTree(TreeNode* root) {
            int path = 0;
            traverseTree(root, path);
            return path;
        }
        
        void traverseTree(TreeNode* root, int& pathMax) {
            if (!root) return;
            if (!root->left && !root->right) return;
            pathMax = max(pathMax, diameterOfNode(root));
            traverseTree(root->left, pathMax);    
            traverseTree(root->right, pathMax);
        }
        
        int diameterOfNode(TreeNode* node) {
            return maxHeight(node->left) + maxHeight(node->right); 
        }
        int maxHeight(TreeNode* node) {
            if (!node) return 0;
            return 1 + max(maxHeight(node->left),maxHeight(node->right));
        }
    

Log in to reply
 

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