二分木が与えられる。
頂点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; } };