An intuitive divide-and-conquer solution


  • 0
    X

    For more info, please refer to my blog post.

    class Solution {
    public:
        int maxPathSum(TreeNode *root) {
            int height, diameter;
     
            treeHeightDiameter(root, height, diameter);
            return diameter;
        }
        /**
         *  divide & conquer: two farthest nodes are such that
         *  0) root is in the path
         *  root is not, two cases
         *  1) both in the left tree
         *  2) right
         */
        // @param height: longest distance from a node to root, including root itself; not necessarily a leaf bcoz val can be negative
        // @param diameter: longest distance between two nodes in the tree
        void treeHeightDiameter(TreeNode *root, int &height, int &diameter) {
            int l_height = -10000;
            int l_diameter = -10000;
            int r_height = -10000;
            int r_diameter = -100000;
             
            if (!root) {
                height = 0;
                diameter = 0;
                return;
            }
            if (!root->left && !root->right) {
                height = root->val;
                diameter = root->val;
                return;
            }
     
            if (root->left)
                treeHeightDiameter(root->left, l_height, l_diameter);
            if (root->right)
                treeHeightDiameter(root->right, r_height, r_diameter);
     
            height = max(l_height, r_height);
            height = (height > 0) ? (height + root->val) : root->val;
     
            diameter = root->val;
            if (l_height > 0)
                diameter += l_height;
            if (r_height > 0)
                diameter += r_height;
            diameter = max(diameter, l_diameter);
            diameter = max(diameter, r_diameter);
        }
    };
    

Log in to reply
 

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