はまやんはまやんはまやん

hamayanhamayan's blog

Maximum Difference Between Node and Ancestor [LeetCode 1026]

https://leetcode.com/contest/weekly-contest-132/problems/maximum-difference-between-node-and-ancestor/

二分木が与えられる。
頂点Aが頂点Bの祖先であるときの、abs(A.val - B.val)の最大値を求めよ。

頂点数≦5000
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

解説

https://leetcode.com/contest/weekly-contest-132/submissions/detail/222247210/

頂点数を見てみると、ある頂点について祖先の頂点を全探索しても間に合うので、全ての頂点のペアを全探索して、答えを探していく。
全探索の方法として、vectorを使う方法がある。
ある頂点に入った時に自分のvalをvector末尾に追加して、出るときにvector末尾(自分のval)から出すことで、ある頂点に入ったときにvectorに入っているのが祖先のvalになっている。
これを見て、最大値を求めていこう。

class Solution {
public:
	int ans = 0;
	vector<int> prev;
	void dfs(TreeNode* cur) {
		if (cur == NULL) return;
		fore(i, prev) chmax(ans, abs(i - cur->val));
		prev.push_back(cur->val);
		
		dfs(cur->left);
		dfs(cur->right);

		prev.pop_back();
	}
	int maxAncestorDiff(TreeNode* root) {
		ans = 0;
		dfs(root);
		return ans;
	}
};