카탈로그

589 N 갈래 나무의 앞부분을 두루 훑어본다

144 두 갈래 나무의 앞자리가 두루 다닌다

98 두 갈래 검색 트리 검증

102 두 갈래 나무의 층계가 두루 다닌다

589 N 포크 트리의 앞 순서 반복

난이도

class Solution {
public:
    vector<int> preorder(Node* root) {
        if(root)
        {
            res.push_back(root->val);
            for(auto node:(*root).children)
                preorder(node);
        }
        return res;
    }   
private:
    vector<int> res; 
    stack<Node *> 
};

법2, 정상적인 교체, 창고를 빌리다

class Solution {
public:
    vector<int> preorder(Node* root) {
        if(!root)
            return res;
        temp.push(root);
        while(!temp.empty())
        {
            Node *node = temp.top();
            temp.pop();
            if(node)
                res.emplace_back(node->val);
            else
                continue;
            if(!node->children.empty())
            for(int i=node->children.size()-1;i>=0; i--)
                temp.push(node->children[i]);
        }
        return res;
    }   
private:
    vector<int> res; 
    stack<Node*> temp;
};

144 두 갈래 나무의 앞길이 두루 다니다

귀속은 말하지 않겠다. 여기에 비귀속 코드를 동봉한다https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/miao-sha-quan-chang-ba-hou-lang-by-sonp/

98 인증 두 갈래 검색 트리

중등 방법1: 먼저 중간 순서를 두루 훑어보고 하나의 서열을 얻어 이 서열이 점차적으로 증가하는지 보는 것은 일반적인 사고방식에 속한다

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(!root)
            return true;
        buildRes(root);
        for(int i=0;i<res.size()-1;i++)
            if(!(res[i] < res[i+1]))
                return false;
        return true;        
    }
    void buildRes(TreeNode* root)
    {
        if(root)
        {
            buildRes(root->left);
            res.emplace_back(root->val);
            buildRes(root->right);
        } 
    }
private:
    vector<int> res;
};

방법2: 모든 노드의 값은lower와 upper 사이에 있어야 한다. 왼쪽 트리를 훑어볼 때 upper는 루트 노드이고, 오른쪽 트리를 훑어볼 때 lower는 루트 노드이다.

class Solution {
public:
    bool helper(TreeNode* root, long long lower, long long upper) {
        if (root == nullptr) return true;
        if (root -> val <= lower || root -> val >= upper) return false;
        return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);
    }
    bool isValidBST(TreeNode* root) {
        return helper(root, LONG_MIN, LONG_MAX);
    }
};

102 두 갈래 나무의 층계가 두루 다니다

중등 방법 1. 대열의 두 가지 기법을 빌리고 기법 하나는 자신의 방법이다. 두 가지 기법의 사고방식은 똑같다. 모두 대열을 빌리는 것이다. 그러나 나의 기법은 비공 노드를 대열에 넣는 것이다. 기법 둘은 모두 대열에 들어가고 대열을 나갈 때 8ms11.7MB를 판단한다.

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root)
            return res;
        myque.push(root);
        while(!myque.empty())
        {
            vector<int> temp;
            int size = myque.size();
            for(int i=0;i<size;i++)
            {
                temp.emplace_back(myque.front()->val);
                if(myque.front()->left)
                    myque.push(myque.front()->left);
                if(myque.front()->right)
                    myque.push(myque.front()->right);
                myque.pop();
            }
            res.emplace_back(temp);
           
        }
        return res;        
    }
private:
    queue<TreeNode *> myque;
    vector<vector<int>> res;
};

쓰기 2 참고 문제 풀이 4ms 11.8MB

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        /*if(!root)
            return res;*/
        myque.push(root);
        while(!myque.empty())
        {
            vector<int> temp;
            int size = myque.size();
            while(size--)
            {
                TreeNode *node = myque.front();
                myque.pop();
                if(!node)
                    continue;
                temp.emplace_back(node->val);
                myque.push(node->left);
                myque.push(node->right);
                
            }
            if(!temp.empty())
            res.emplace_back(temp);
           
        }
        return res;        
    }
private:
    queue<TreeNode *> myque;
    vector<vector<int>> res;
};

방법2: 깊이가 우선이고 위의 방법1은 넓이가 우선이지만 정상적으로 말하자면 넓이가 우선인 것은 한 길을 따라 끝까지 걷고 다시 돌아보는 것이다. 이것은 선순이 반복되는 것과 매우 비슷하다. 그러나 여기서 어떻게 어떤 노드가 같은 층에 있는지 알 수 있겠는가? 변수level을 통해 표기

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        buildRes(res, root, 0);
        return res;        
    }
    void buildRes(vector<vector<int>>& vec, TreeNode *root, int level)
    {
    	// ， 
        if(!root)
            return;
        // ：
        	 ， vector 
        if(level >= vec.size())
            vec.emplace_back(vector<int>());
        vec[level].emplace_back(root->val);
        //    level 
        buildRes(vec, root->left, level+1);
        buildRes(vec, root->right, level+1);
    }
private:
    queue<TreeNode *> myque;
    vector<vector<int>> res;
};