C++_0ms_Accepted & Follow up


  • 0

    It is a problem to calculate the height of each node.

    class Solution {
    public:
    vector<vector<int>> findLeaves(TreeNode* root) {
        vector<vector<int>> res;
        height(res, root);
        return res;
    }
    
    int height(vector<vector<int>>& res, TreeNode* root){
        if(root == nullptr) return 0;
        int value = root->val;
        int H = 1 + max(height(res, root->left), height(res, root->right));
        if(H > res.size()){
            vector<int> path;
            path.push_back(value);
            res.push_back(path);
        }else{
            res[H-1].push_back(value);
        }
        return H;
    }
    };
    

    Also we can change this question as we want put the node with the same depth into the same level in the vector.

    Code:

    class Solution {
    public:
    vector<vector<int>> findLeaves(TreeNode* root) {
        vector<vector<int>> res;
        depth(res, root, 0);
        return res;
    }
    
    void depth(vector<vector<int>>& res, TreeNode* root, int D){
        if(root == nullptr){return;}
        if(D >= res.size()){
           vector<int> path;
           path.push_back(root->val);
           res.push_back(path);
        }else{
           res[D].push_back(root->val);
        }
        depth(res, root->left, D+1);
        depth(res, root->right, D+1);
        return;
    }
    };
    
    //input: [1,2,3,4,5,null,6,null,null,null,7]
    //result: [[1],[2,3],[4,5,6],[7]]

Log in to reply
 

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