[LeetCode] 144. Binary Tree Preorder Traversal

https://leetcode.com/problems/binary-tree-preorder-traversal

Tree가 주어질 경우 이 값을 root부터 순차적으로 값을 배열에 저장하는 심플한 문제이다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> answer;
        TreeNode* current = root;
        vector<TreeNode*> parents;
        int count = 0;
        if(root == nullptr) {
            return answer;
        }
        do {
            if(current->val > -101) {
                answer.push_back(current->val);
                current->val = -101;
            }

            if(current->left != nullptr) {
                parents.push_back(current);
                current = current->left;
                parents.back()->left = nullptr;
            } else if(current->right != nullptr) {
                parents.push_back(current);
                current = current->right;
                parents.back()->right = nullptr;
            } else if (!parents.empty()) {
                current = parents.back();
                parents.pop_back();
            }
            if(parents.empty()) {
                ++count;
            }
        } while(count < 2);

        return answer;
    }
};

-100~100의 값을 가지는 조건이어서 지나갈 경우 지나간 표시로 그 외의 값을 넣어 주고 부모들을 모아 두는 벡터에 저장한다.

이후에 left부터 순회하면서 값을 저장하도록 하였다.

https://leetcode.com/problems/binary-tree-postorder-traversal

155번 문제는 후위로 담는 문제로, 거꾸로 자식 노드부터 넣도록 하면 되는데 위 코드와 유사한 점이 많다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> answer;
        TreeNode* current = root;
        vector<TreeNode*> parents;
        int count = 0;
        if(root == nullptr) {
            return answer;
        }
        do {
            if(current->left != nullptr) {
                parents.push_back(current);
                current = current->left;
                parents.back()->left = nullptr;
            } else if(current->right != nullptr) {
                parents.push_back(current);
                current = current->right;
                parents.back()->right = nullptr;
            } else {
                if(current->val > -101) {
                    answer.push_back(current->val);
                    current->val = -101;
                }
                if (!parents.empty()) {
                    current = parents.back();
                    parents.pop_back();
                }
            }
            if(parents.empty()) {
                ++count;
            }
        } while(count < 3);

        return answer;
    }
};