두 갈래 나무와 그림

두 갈래 나무 깊이 검색

1. 경로 총 II

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector> pathSum(TreeNode* root, int sum) {
        vector> result;
        vector path;
        int path_value = 0;
        pathSum(root, path_value, sum, path, result);
        return result;
    }
    
    void pathSum(TreeNode* node, int& path_value, int sum, vector& path, vector>& result)
    {
        if( !node )
        {
            return ;
        }
        
        path_value += node->val;        //   
        path.push_back(node->val);
        
        if( (!node->left) && (!node->right) && (path_value == sum) )
        {
            result.push_back(path);
        }
        
        pathSum(node->left, path_value, sum, path, result);
        pathSum(node->right, path_value, sum, path, result);
        
        path_value -= node->val;        //  
        path.pop_back();
    }
};

2. 두 갈래 나무의 최근 조상

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* result = NULL;
        vector path;                 //  
        vector p_path;               //  p 
        vector q_path;               //  q 
        bool flag = false;                      //  
        
        pathWay(root, p, path, p_path, flag);   //  p_path
        path.clear();                           //  path， q 
        flag = false;
        pathWay(root, q, path, q_path, flag);   //  q_path
        int len = (p_path.size() <= q_path.size()) ? p_path.size() : q_path.size();
        for(int i = 0; i < len; ++i)
        {
            if( p_path[i] == q_path[i] )
            {
                result = p_path[i];
            }
        }
        
        return result;
    }
    
    void pathWay(TreeNode* node, TreeNode* search_node, vector& path, vector& search_path , bool& flag)
    {
        if( !node || flag )
        {
            return ;
        }
        
        path.push_back(node);
        if( search_node == node )
        {
            search_path = path;
            flag = true;
        }
        
        pathWay(node->left, search_node, path, search_path, flag);
        pathWay(node->right, search_node, path, search_path, flag);
        path.pop_back();        
    }
};

3. 두 갈래 나무는 체인 시계로 펼친다

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* last = NULL;
        preorder(root, last);
        return ;
    }
    
    void preorder(TreeNode* node, TreeNode*& last)
    {
        if( !node )
        {
            return ;
        }
        
        if( !node->left && !node->right )       //  
        {
            last = node;
            return ;
        }
        
        TreeNode* left_node = node->left;
        TreeNode* right_node = node->right;
        TreeNode* left_last = NULL;
        TreeNode* right_last = NULL;
        
        if( left_node )
        {
            preorder(left_node, left_last);
            node->left = NULL;
            node->right = left_node;
            last = left_last;
        }
        
        if( right_node )
        {
            preorder(right_node, right_last);
            if( left_last )
            {
                left_last->right = right_node;
            }
            
            last = right_last;
        }
        
    }
};

두 갈래 나무 층이 두루 다니다

4. 두 갈래 나무의 오른쪽 보기

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector rightSideView(TreeNode* root) {
        vector result;
        queue q;
        
        if( root )
        {
            q.push(root);
        }
        
        while( !q.empty() )
        {
            int len = q.size();
            for(int i=0; ival);
                }
                
                if( node->left )
                {
                    q.push(node->left);
                }
                
                if( node->right )
                {
                    q.push(node->right);
                }
            }
        }
        
        return result;
    }
};

그림의 깊이 검색 / 폭 검색

5. 강좌표

struct GraphNode    //  
{   
    int label;        //  
    vector neighbors;   //  
    GraphNode(int x) : label(x){};  //  
};

class Solution {
public:
    bool canFinish(int numCourses, vector>& prerequisites) {
        vector graph;       //  
        vector degree;             //  
        
        for(int i=0; ineighbors.push_back(end);
            degree[prerequisites[i].first]++;
        }
        
        queue q;
        for(int i=0; ilabel] == 0 )
            {
                q.push(graph[i]);
            }
        }
        
        while( !q.empty() )                             //  queue 
        {
            GraphNode* node = q.front();
            q.pop();
            for(int i=0; ineighbors.size(); ++i)
            {
                degree[node->neighbors[i]->label]--;
                if( degree[node->neighbors[i]->label] == 0 )
                {
                    q.push(node->neighbors[i]);
                }
            }
        }
        
        for(int i=0; i0 )               
            {
                return false;
            }
        }
        
        return true;
    }
};