Leetcode 515. 각 트리 행에서 최대값 찾기

1435 단어 Leetcode

두 갈래 나무의 줄마다 가장 큰 값을 찾아야 합니다.
예:
 : 

          1
         / \
        3   2
       / \   \  
      5   3   9 

 : [1, 3, 9]

기본 사고방식: 두 갈래 나무의 층계가 두루 훑어볼 뿐이다.두 개의 수조로 매번 훑어보는 결과를 교대로 기록하고 최대 값을 결과에 저장합니다.

class Solution {
public:
	vector largestValues(TreeNode* root) {
		vector Res;
		int Max = INT_MIN;
		if (root == NULL) return Res;
		vector First,Second;
		First.push_back(root);
		Res.push_back(root->val);
		while (First.size() != 0 || Second.size() != 0) {
            
            //  
			for (TreeNode* TN : First) {
				if (TN->left != NULL) {
					Second.push_back(TN->left);
					Max = max(Max, TN->left->val);
				}
				if (TN->right != NULL) {
					Second.push_back(TN->right);
					Max = max(Max, TN->right->val);
				}
			}
			if (Second.size() != 0) {
				Res.push_back(Max);
			}
			First.clear();
			Max = INT_MIN;
            
            //  
			for (TreeNode* TN : Second) {
				if (TN->left != NULL) {
					First.push_back(TN->left);
					Max = max(Max, TN->left->val);
				}
				if (TN->right != NULL) {
					First.push_back(TN->right);
					Max = max(Max, TN->right->val);
				}
			}
			if (First.size() != 0) {
				Res.push_back(Max);
			}
			Second.clear();
			Max = INT_MIN;
		}
		return Res;
	}
};

좋은 웹페이지 즐겨찾기