My C++ solution, Preorder Traversal, 16ms


  • 0
    W
    class Solution {
    public:
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            vector<vector<int>> result;
            if(root == NULL) return result;
            stack<pair<TreeNode*, int>> st;
            vector<int> path;
            st.emplace(root, 1);
            int total = 0;
            while(!st.empty()) {
                pair<TreeNode*, int> top = st.top();
                st.pop();
                TreeNode* node = top.first;
                int depth = top.second;
                while(path.size() > depth - 1) {
                    total -= path.back();
                    path.pop_back();
                }
                path.push_back(node->val);
                total += node->val;
                if(node->left == NULL && node->right == NULL) {
                    if(sum == total) result.push_back(path);
                    continue;
                }
                if(node->right) st.emplace(node->right, depth + 1);
                if(node->left) st.emplace(node->left, depth + 1);
            }
            return result;
        }
    };
    

  • 0
    L

    @wjbnys beautiful code


Log in to reply
 

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