LeetCode 366. 두 갈래 나무의 잎 노드 찾기(위아래로 두 갈래 나무 뒤집기 + BFS)

기사 목록

1. 제목

2. 문제 풀이

1. 제목

두 갈래 나무 한 그루를 드리겠습니다. 다음 순서에 따라 모든 노드를 수집하십시오.

순서대로 왼쪽부터 매번 모든 잎 노드를 수집하고 삭제

나무 전체가 비어 있을 때까지 위의 과정을 반복

 :
 : [1,2,3,4,5]
  
          1
         / \
        2   3
       / \     
      4   5    

 : [[4,5,3],[2],[1]]
 
 :

1.   [4,5,3] ， ：

          1
         / 
        2          
 

2.   [2] ， ：

          1          
 

3.   [1] ， ：

          []         

출처: 리코드(LeetCode) 링크:https://leetcode-cn.com/problems/find-leaves-of-binary-tree저작권은 인터넷 소유에 귀속된다.상업 전재는 정부에 연락하여 권한을 부여하고, 비상업 전재는 출처를 명시해 주십시오.

2. 문제 풀기

제목: LeetCode 156.위아래로 두 갈래 트리 뒤집기(DFS)*

먼저 밑에서 위로 두 갈래 나무를 뒤집고 자 노드의 left를 부모 노드를 가리킨다

부모 노드가 몇 개의 하위 노드가 있는지 동시에 기록한다(0,1,2,)

잎 노드를 대열에 넣기

BFS를 시작하여 한 팀을 내면 이 노드의 left(원래 부모 노드의 하위 노드 계수-1)

노드의 하위 노드가 0으로 계산되면 잎 노드가 되어 입대할 수 있다

class Solution {
    vector<vector<int>> ans;
    queue<TreeNode*> q;
    unordered_map<TreeNode*, int> map;// 
public:
    vector<vector<int>> findLeaves(TreeNode* root) {
        reverse(root);// 
        while(!q.empty())
        {
        	int size = q.size(), i = 0;
        	vector<int> lv(size);
        	while(size--)
        	{
        		TreeNode *cur = q.front();
        		q.pop();
        		map[cur->left]--;// -1
        		lv[i++] = cur->val;// 
        		if(cur->left && map[cur->left]==0)// 0， 
        			q.push(cur->left);
        	}
        	ans.push_back(lv);
        }
        return ans;
    }
    TreeNode* reverse(TreeNode* root)
    {
    	if(!root) return NULL;
    	auto l = root->left;
    	auto r = root->right;
    	if(!l && !r)
    		q.push(root);// 
    	map[root] += (l?1:0) + (r?1:0);// ， 
    	root->left = NULL;// 
    	root->right = NULL;
    	auto lc = reverse(l);
    	auto rc = reverse(r);
    	if(lc)
    		lc->left = root;// left 
    	if(rc)
    		rc->left = root;
    	return root;
    }
};

0 ms 9 MB

위의 방법은 나무를 두 번 훑어보았고, 더욱 간단한 방법은 나무의 높이(2측자수의 최대 높이 + 1 자신)에 따라 그룹을 나누었다

class Solution {
    vector<vector<int>> ans;
public:
    vector<vector<int>> findLeaves(TreeNode* root) {
        dfs(root);
        return ans;
    }
    int dfs(TreeNode* root)
    {
        if(!root) return -1;
        int hl = dfs(root->left);
        int hr = dfs(root->right);
        int hcur = max(hl, hr) + 1;
        if(ans.size() <= hcur)
            ans.push_back({});
        ans[hcur].push_back(root->val);
        return hcur;
    }
};

4 ms 9.1 MB
내 CSDN 블로그 주소https://michael.blog.csdn.net/
길게 누르거나 스캔해서 나의 공중호(마이클 아명)를 팔로우하고, 함께 힘내고, 함께 공부하고, 진보하자!