Two simple different methods in C++ 4ms, update


  • 0
    M

    1. pass string copy, it may waste some memory

    class Solution {
    public:
        vector<string> ans;
        vector<string> binaryTreePaths(TreeNode* root) {
            if(root!=NULL) helper(root, "");
            return ans;
        }
        void helper(TreeNode* node, string s){
            s += s.empty() ? to_string(node->val) : "->" + to_string(node->val);
            if(!node->left && !node->right){
                ans.push_back(s);
                return;
            }
            if(node->left!=NULL) helper(node->left, s);
            if(node->right!=NULL) helper(node->right, s);
        }
    };
    

    2. use global string s, change its size during traverse

    class Solution {
    public:
        vector<string> ans;
        string s;
        vector<string> binaryTreePaths(TreeNode* root) {
            if(root!=NULL) helper(root);
            return ans;
        }
        void helper(TreeNode* node){
            int oldSize = s.size();
            s += s.empty() ? to_string(node->val) : "->" + to_string(node->val);
            if(!node->left && !node->right){
                ans.push_back(s);
                s.resize(oldSize);
                return;
            }
            if(node->left!=NULL) helper(node->left);
            if(node->right!=NULL) helper(node->right);
            s.resize(oldSize);
        }
    };
    

    update: Find out the maximum sum of value from root to each leaf in a binary tree.

    int findMax(TreeNode *root){ //from root to each leaf
        if (root==NULL)
            return 0;
        else
            return max((findMax(root->left), findMax(root->right)) + root->val;
    }
    

    This update question is much easier than Binary Tree Maximum Path Sum.


Log in to reply
 

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