두 갈래 나무 제목 집합

Leecode.617. 두 갈래 나무 합병

두 갈래 나무를 정해라. 그들 중 하나를 다른 나무로 덮으면 두 갈래 나무의 일부 노드가 겹칠 것이라고 상상해라.너는 그들을 새로운 두 갈래 나무로 합쳐야 한다.결합의 규칙은 두 노드가 중첩되면 그들의 값을 노드가 합쳐진 후의 새로운 값으로 추가하는 것이다. 그렇지 않으면 NULL이 아닌 노드는 새로운 두 갈래 나무의 노드로 직접 사용된다.
사고방식: 앞차례 두루 훑어보다

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(t1==NULL) return t2;
        if(t2==NULL) return t1;
        t1->val+=t2->val;
        t1->left=mergeTrees(t1->left,t2->left);
        t1->right=mergeTrees(t1->right,t2->right);
        return t1;
    }
};

Leecode.572. 다른 나무의 자목

생각: dfs

class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if(dfs(s,t)) return true;
        return isSubtree(s->left,t)||isSubtree(s->right,t);
        
    }
    bool dfs(TreeNode*s,TreeNode*t){
        if(s==nullptr&&t==nullptr) return true;
        if(s==nullptr||t==nullptr) return false;
        if(s->val!=t->val) return false;
        return dfs(s->left,t->left)&&dfs(s->right,t->right);
    }
};

Leecode.124. 두 갈래 나무의 최대 경로와

비공 두 갈래 트리를 지정하고 최대 경로와 를 되돌려줍니다.본고에서 경로는 나무의 임의의 노드에서 출발하여 임의의 노드에 도달하는 서열로 정의되었다.이 경로는 최소한 하나의 노드를 포함하고 루트 노드의 예시를 거치지 않습니다. 입력: [1,2,3] 출력: 6
사고방식: 위에서 아래로 반복, 최대 경로와 네 가지 상황:

left - root - right

left - root

root - right

루트가 주의해야 할 것은 돌아올 때 현재 노드가 왼쪽 트리나 오른쪽 트리 중 하나로 가는 경로이고 전역 변수로 최대 경로와..

class Solution {
public:
    int maxsum;
    int maxPathSum(TreeNode* root) {
        if(root==NULL) return 0;
        maxsum=root->val;
        dfs(root);
        return maxsum;                        
    }
    int dfs(TreeNode* root){
        if(root==NULL) return 0;
        int leftmax=max(0,dfs(root->left));
        int rightmax=max(0,dfs(root->right));
        maxsum=max(root->val+leftmax+rightmax,maxsum);
        return max(root->val+leftmax,root->val+rightmax);
    }
};

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

두 갈래 나무를 정해서 오른쪽에 서 있는 것을 상상하고 꼭대기에서 끝까지 순서대로 오른쪽에서 볼 수 있는 노드 값을 되돌려줍니다.입력: [1,2,3,null, 5,null, 4] 출력: [1,3,4]
사고방식: 보이는 것은 각 층의 가장 오른쪽 노드이기 때문에 차원을 이용하여 두루 훑어보아야 한다

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int>res;
        if(root==NULL) return res;
        queue<TreeNode*>q;
        q.push(root);
        while(!q.empty()){
            int size=q.size();
            res.push_back(q.front()->val);
            while(size--){
                TreeNode*tmp=q.front();
                q.pop();
                if(tmp->right) q.push(tmp->right);
                if(tmp->left) q.push(tmp->left);
            }
        }
        return res;
    }
};

Leecode.98. 두 갈래 검색 트리 검증

사고방식: 귀착, 경계 조건 주의

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return dfs(root, LONG_MIN, LONG_MAX);
    }
    bool dfs(TreeNode*root,long long min,long long max){
        if(root==NULL) return true;
        if(root->val<=min||root->val>=max) return false;
        return dfs(root->left,min,root->val)&&dfs(root->right,root->val,max);
    }
};