[검지 Offer] 두 갈래 트리 중 하나가 되는 경로

문제 설명

알고리즘 분석

코드 구현

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/
class Solution {
public:
    vector<vector<int> > FindPath(TreeNode* root, intexpectNumber) {
        vector<vector<int> > result;
        if(root == NULL) {
            return result;
        }
        int data = root->val;
        if(expectNumber < data) {
            return result;
        }

        elseif(expectNumber == data) {
            vector<int> x;
            x.push_back(data);
            result.push_back(x);
        }

        else{
            expectNumber -= data;
            bool left = findPath(&result, root->left, expectNumber);
            bool right = findPath(&result, root->right, expectNumber);
            if( left || right ) {
                for(int i = 0; i < result.size(); i++) {
                    result[i].push_back(data);
                    reverse(&(result[i]));
                }
            }
        }
        return result;
    }

    bool findPath(vector<vector<int> >* result, TreeNode* root, intexpectNumber) {
        if(root == NULL && expectNumber == 0) {
            return true;
        }
        elseif(root == NULL) {
            return false;
        }

        int data = root->val;

        if(expectNumber < data) {
            return false;
        }

        elseif(expectNumber == data&& root->left == NULL && root->right == NULL) {
            vector<int> x;
            x.push_back(data);
            result->push_back(x);
        }

        else{
            expectNumber -= data;
            vector<vector<int> > left;
            bool bLeft = findPath(&left, root->left, expectNumber);
            if(bLeft) {
                for(inti = 0; i < left.size(); i++) {
                    left.at(i).push_back(data);
                    result->push_back(left[i]);
                }
            }
            vector<vector<int> > right;
            bool bRight = findPath(&right, root->right, expectNumber);
            if(bRight) {
                for(int i = 0; i < right.size(); i++) {
                    right.at(i).push_back(data);
                    result->push_back(right[i]);
                }
            }
        }

        return result;
    }

    void reverse(vector<int>* v) {
        int size = v->size();
        int half = size / 2;
        for(inti = 0; i < half; i++) {
            int tmp = v->at(i);
            v->at(i) = v->at(size - i - 1);
            v->at(size - i - 1) = tmp;
        }
    }
};