LeetCode Solutions
971. Flip Binary Tree To Match Preorder Traversal
Time: $O(n)$ Space: $O(h)$
class Solution {
public:
vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
vector<int> ans;
dfs(root, 0, voyage, ans);
return ans;
}
private:
void dfs(TreeNode* root, int&& i, const vector<int>& voyage,
vector<int>& ans) {
if (root == nullptr)
return;
if (root->val != voyage[i++]) {
ans.clear();
ans.push_back(-1);
return;
}
if (i < voyage.size() && root->left && root->left->val != voyage[i]) {
// Flip root
ans.push_back(root->val);
dfs(root->right, move(i), voyage, ans);
dfs(root->left, move(i), voyage, ans);
} else {
dfs(root->left, move(i), voyage, ans);
dfs(root->right, move(i), voyage, ans);
}
}
};
class Solution {
public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
List<Integer> ans = new ArrayList<>();
dfs(root, voyage, ans);
return ans;
}
private int i = 0;
private void dfs(TreeNode root, int[] voyage, List<Integer> ans) {
if (root == null)
return;
if (root.val != voyage[i++]) {
ans.clear();
ans.add(-1);
return;
}
if (i < voyage.length && root.left != null && root.left.val != voyage[i]) {
// Flip root
ans.add(root.val);
dfs(root.right, voyage, ans);
dfs(root.left, voyage, ans);
} else {
dfs(root.left, voyage, ans);
dfs(root.right, voyage, ans);
}
}
}