C++ variation of height


  • 0
    B

    previous height help function return a pair of height on left and right hand side.

    Now we can return an array of elements to tell the max height and current best diameter

    
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        int diameterOfBinaryTree(TreeNode* root) {
            auto e = help(root);
            return e[2];
        }
        
        //return a vector of three int
        //the first element is the longest edge on the left side
        //the second element is the longest edge on the right side
        //the thrid element is current best diameter
        vector<int> help( TreeNode * root)
        {
            vector<int>ans(3,0);
            if(!root) return ans;
            if(root -> left) ans[0] = 1;
            if(root -> right) ans[1] = 1;
            auto left = help(root -> left);
            auto right = help(root -> right);
            
            if(left[0] || left[1]) ans[0] = max( ans[0], max(left[0], left[1])+1);
            if(right[0] || right[1]) ans[1] = max( ans[1], max(right[0], right[1])+1);
            ans[2] = max(ans[0] + ans[1], max(left[2], right[2]));
            return ans;
        }
    };

Log in to reply
 

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