257. Binary Tree Paths - cocoder39/coco39_LC GitHub Wiki

257. Binary Tree Paths

dfs, O(n) time and O(height) space for call stack. More detailed time complexity analysis: because of string copy, real time is O(n ^ 2). the root node value would be copied n times, second level node(s) would be copied n-1 times... worst case is O(n + n-1 + .. 1) (link a linked list) = O(n ^ 2). We can estimate the longest string length and pre-allocate enough memory for path

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

iterative dfs+stack

vector<string> binaryTreePaths(TreeNode* root) {
        if (! root) {
            return {};
        }

        vector<string> res;
        stack<TreeNode*> nodeSt;
        stack<string> strSt;
        nodeSt.push(root);
        strSt.push(to_string(root->val));
        while (! nodeSt.empty()) {
            TreeNode* node = nodeSt.top();
            nodeSt.pop();
            string str = strSt.top();
            strSt.pop();

            if (! node->left && ! node->right) {
                res.push_back(str);
            } else {
                if (node->right) {
                    nodeSt.push(node->right);
                    strSt.push(str + "->" + to_string(node->right->val));
                }
                if (node->left) {
                    nodeSt.push(node->left);
                    strSt.push(str + "->" + to_string(node->left->val));
                } 
            }
        }
        return res;
    }

iterative bfs+queue

vector<string> binaryTreePaths(TreeNode* root) {
        if (! root) {
            return {};
        }
        
        vector<string> res;
        queue<TreeNode*> nodeQu;
        queue<string> strQu;
        nodeQu.push(root);
        strQu.push(to_string(root->val));
        while (! nodeQu.empty()) {
            TreeNode* node = nodeQu.front();
            nodeQu.pop();
            string str = strQu.front();
            strQu.pop();
            
            if (! node->left && ! node->right) {
                res.push_back(str);
            } else {
                if (node->left) {
                    nodeQu.push(node->left);
                    strQu.push(str + "->" + to_string(node->left->val));
                } 
                if (node->right) {
                    nodeQu.push(node->right);
                    strQu.push(str + "->" + to_string(node->right->val));
                }
            }
        }
        return res;
    }
⚠️ **GitHub.com Fallback** ⚠️